edward_mj

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2006
【算法分析】
就是搞成前缀和数组以后写一个rmq。然后在外面套一个二叉堆每次取最大值。然后把取出的区间裂解成两半，去掉中间那个最小值元素，继续放进二叉堆里，这样就可以AC。
T_T时间排在第3名。前面两个都是JZP神牛。
【时间复杂度】O((n+m) lg (n+m))
【空间复杂度】O(n lg n + n+m)
【吐槽】
NOI的时候写得二分答案+平衡树被卡得只剩30分T_T。。。
现在高3一个月只能回一次家。。。本次是因为配眼镜为由请假回家，就找些题练练手= =，准备我巨重要的NOIP。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
const int N=500005;
int n,m,low,high;
int a[N];
int lg[N];
int zz[19][N];
lld ST[19][N];

int Get(int l,int r){
int k=lg[r-l+1];
if (ST[k][l] else return zz[k][r-(1<}

struct Heap_t{
struct Node{int l,r,i;lld key;}Q[N+N];
int tot;

void up(int k){
while (k>1 && Q[k>>1].key swap(Q[k>>1],Q[k]);
k>>=1;
}
}

void down(int k){
int p;
while (k<<1<=tot){
p=k<<1;
if (p if (Q[p].key>Q[k].key){
swap(Q[p],Q[k]);
k=p;
}
else break;
}
}

void Insert(int l,int r,int i){
if (l>r) return;
tot++;
Q[tot].l=l; Q[tot].r=r; Q[tot].i=i; Q[tot].key=ST[0][i]-ST[0][Get(l,r)];
up(tot);
}

void Del(){
Node tmp=Q[1];
Q[1]=Q[tot–];
down(1);
int pos=Get(tmp.l,tmp.r);
Insert(tmp.l,pos-1,tmp.i);
Insert(pos+1,tmp.r,tmp.i);
}

void init(){
int i;
for (tot=0,i=1;i<=n;i++)
Insert(max(0,i-high),i-low,i);
}

void solve(){
lld ans=0;
while (m){
ans+=Q[1].key;
Del();
m–;
}
printf("%I64dn",ans);
}
}Heap;

void init(){
scanf("%d%d%d%d",&n,&m,&low,&high);
int k,s,i;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) {ST[0][i]=ST[0][i-1]+a[i]; zz[0][i]=i;}
for (k=1;1< s=1< for (i=0;i+s+s-1<=n;i++)
if (ST[k-1][i] ST[k][i]=ST[k-1][i];
zz[k][i]=zz[k-1][i];
}
else{
ST[k][i]=ST[k-1][i+s];
zz[k][i]=zz[k-1][i+s];
}
}
for (i=1,k=0;i<=n;i++)
lg[i]=k+=(i==(1<}

int main(){
init();
Heap.init();
Heap.solve();
}

【题目大意】

给定n个物品，第i个物品有三个属性Ai,Bi,Ci。然后把这个n个物品分别分到3个集合中（集合可以为空），使得A集合中的物品的Max{Ai}+B集合中的物品的Max{Bi}+C集合中物品的Max{Ci}最小。（空集算作0）

【算法分析】

HDOJ3552是只有两个属性，那么按Ai排序，然后枚举Max{Ai}。然后剩下的另一边的Max{Bi}加起来就是当前值。

然后对于本题。依然按Ai排序，仍然从大到小枚举Max{Ai}。然后对剩下的另一边维护上面那个问题。

显然，若存在Bi<=Bj Ci<=Cj，那么i这个物品就没用了。那么我们可以维护一个线性表，使得他关于Bi递增。同时，删掉多余的物品以后，关于Ci递减。那么很显然，我们取某一个物品截开，那么这边取的值就是Bi+C_i+1，然后这种动态线性表显然就可以用平衡树维护。然后为了比较方便找前驱和后继，我用了Splay。

【其它】1Y。这次把Splay函数和rotate函数压了代码，Splay只有两个rotate，rotate里不用分类讨论。

【CODE】

#include

#include

#include

#include

#include

using namespace std;

const int N=105555;

const int INF=1000000000;

int n,root;

struct Node{int x,y,z;}a[N];

int pre[N],best[N],w[N],ch[N][2];

bool cmp(const Node &A,const Node &B){

     return A.x

}

void init(){

     int i;

     scanf("%d",&n);

     for (i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

     sort(a+1,a+n+1,cmp);

     memset(ch,0,sizeof(ch));

     memset(pre,0,sizeof(pre));

     root=n+1;

     ch[n+1][0]=n+2;

     pre[n+2]=n+1;

    

     a[n+1].y=INF; a[n+1].z=0;

     a[n+2].y= 0; a[n+2].z=INF;

    

     w[n+1]=INF; best[n+1]=0;

     w[n+2]=best[n+2]=0;

}

void update(int x){

     best[x]=INF;

     if (ch[x][0]) best[x]=min(best[ch[x][0]],best[x]);

     if (ch[x][1]) best[x]=min(best[ch[x][1]],best[x]);

     best[x]=min(w[x],best[x]);

}

void rotate(int x,int T){

     int y=pre[x];

     ch[y][!T]=ch[x][T];

     ch[x][T]=y;

     pre[x]=pre[y];

     pre[y]=x;

     pre[ch[y][!T]]=y;

     if (ch[pre[x]][0]==y) ch[pre[x]][0]=x;

                      else ch[pre[x]][1]=x;

     update(y);

     update(x);

}

void Splay(int x,int goal){

     int y,z;

     if (x==0 || x==goal) return;

     if (goal==0) root=x;

     while (pre[x]!=goal){

           y=pre[x]; z=pre[y];

           if (z!=goal) rotate(ch[z][0]==y^ch[y][0]==x?x:y,ch[y][0]==x);

           rotate(x,ch[pre[x]][0]==x);

     }

}

void Get_next(){

     int p=ch[root][1],q=root;

     while (p){

           q=p;

           p=ch[p][0];

     }

     Splay(q,0);

}

void Get_pre(){

     int p=ch[root][0],q=root;

     while (p){

           q=p;

           p=ch[p][1];

     }

     Splay(q,0);

}

bool Can_Insert(int i){

     int p=root,q;

     while (p){

           q=p;

           p=ch[p][a[p].y

     }

     Splay(q,0);

     if (a[q].y

     if (a[root].y>=a[i].y && a[root].z>=a[i].z) return false;

                                            else return true;

}

void (){

     int p=ch[root][0];

     while (ch[p][1]) p=ch[p][1];

     Splay(p,root);

     ch[p][1]=ch[root][1];

     pre[ch[root][1]]=p;

     pre[p]=0;

     root=p;

}

void Delete_Useless_Node(int i){

     while (1){

       if (a[root].y>a[i].y) Get_pre();

       if (a[root].y<=a[i].y && a[root].z<=a[i].z)

         ();

       else

         break;

     }

}

void Insert(int i){

     int p=root,q;

     while (p){

           q=p;

           p=ch[p][a[p].y

     }

     pre[i]=q;

     ch[q][a[q].y

     Splay(i,0);

     p=ch[i][1];

     while (ch[p][0]) p=ch[p][0];

     w[i]=a[i].y+a[p].z;

     Splay(p,i);

     update(i);

     Get_pre();

     w[root]=a[root].y+a[i].z;

     update(root);

}

void Try_Insert(int i){

     if (!Can_Insert(i)) return;

     Delete_Useless_Node(i);

     Insert(i);

}

    

void work(){

     int i,ans=INF,now;

     a[0].x=0;

     for (i=n;i>=0;i–){

         now=a[i].x;

         now+=best[root];

         if (now

         Try_Insert(i);

     }

     printf("%dn",ans);

}

int main(){

    init();

    work();

    return 0;

}