BZOJ3460: Jc的宿舍【树上莫队】

3460: Jc的宿舍

【题目描述】

传送门

【题解】

树上莫队。
当然从小到大最优。
考虑如何修改,设当前修改第x个人,耗时为T[x],等待时间为Sum[x]。
当然对于所有T[i]>=T[x],Sum[x]+=T[x];
对于x,加上在他之前打水的人的时间,还有在他的时间。
那么就可以用树状数组优化啦。

交了一发,咦,怎么rank2了。

代码如下

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=50005,MAXM=50005;
typedef long long LL;
int n,m,K,KEY,cnt,B,lgn,Al,block[MAXN<<1],Fa[MAXN][20],ID[MAXN<<1],IN[MAXN],OUT[MAXN],Dep[MAXN],a[MAXN],b[MAXN],Num[MAXN];bool T[MAXN];
LL NowAns,Ans[MAXM<<1],f[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN<<1],son[MAXN<<1];
    void Add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
}E;
struct xcw{
    int L,R,fa,id;
    bool operator <(const xcw b)const{return (block[L]<block[b.L]||block[L]==block[b.L]&&((block[L]&1)?R<b.R:R>b.R));}
}W[MAXM<<1];
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
    return f?ret:-ret;
}
void DFS(int x,int fa){
    ID[IN[x]=++cnt]=x;Dep[x]=Dep[fa]+1;Fa[x][0]=fa;
    for(int j=E.lnk[x];j;j=E.nxt[j]) if(E.son[j]!=fa) DFS(E.son[j],x);
    ID[OUT[x]=++cnt]=x;
}
void INIT(){
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) Fa[i][j]=Fa[Fa[i][j-1]][j-1];
}
int LCA(int p,int q){
    if(Dep[p]<Dep[q]) swap(p,q);
    int Del=Dep[p]-Dep[q];
    for(int i=0;(1<<i)<=Del;i++) if(Del&(1<<i)) p=Fa[p][i];
    if(p==q) return p;
    for(int i=lgn;i>=0;i--)
    if(Fa[p][i]!=Fa[q][i]) p=Fa[p][i],q=Fa[q][i];
    return Fa[p][0];
}
void Putf(int x,int p){for(int i=x;i<=n;i+=i&-i) f[i]+=p;}
LL Getf(int x){LL Sum=0;for(int i=x;i;i-=i&-i) Sum+=f[i];return Sum;}
void PutNum(int x,int p){for(int i=x;i<=n;i+=i&-i) Num[i]+=p;}
int GetNum(int x){int Sum=0;for(int i=x;i;i-=i&-i) Sum+=Num[i];return Sum;}
int Chg(int x){
    if(T[x]){
        NowAns-=((LL)Al-GetNum(a[x]-1))*b[a[x]];
        NowAns-=Getf(a[x]-1);
        PutNum(a[x],-1);Putf(a[x],-b[a[x]]);Al--;
    }else{
        PutNum(a[x],1);Putf(a[x],b[a[x]]);Al++;
        NowAns+=((LL)Al-GetNum(a[x]-1))*b[a[x]];
        NowAns+=Getf(a[x]-1);
    }
    T[x]^=1;
}
int main(){
    n=read(),m=read();KEY=read();B=sqrt(2*n);lgn=log2(n);
    for(int i=1;i<=n;i++) b[i]=a[i]=read();
    for(int i=1,x,y;i<=n;i++){int fa=read();E.Add(fa,i),E.Add(i,fa);}
    DFS(1,0);INIT();
    sort(b+1,b+1+n);int D=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+D,a[i])-b;
    for(int i=1;i<=cnt;i++) block[i]=(i-1)/B+1;
    for(int i=1,C=1;i<=m;i++){
        char ch[10];scanf("%s",ch);
        if(ch[0]=='C'){C=read();continue;}
        int P=read();
        int x=C,y=P%n+1,fa=LCA(x,y);
        if(IN[x]>IN[y]) swap(x,y);
        if(fa==x) W[++K]=(xcw){IN[x],IN[y],0,K};
        else W[++K]=(xcw){OUT[x],IN[y],fa,K};
        x=C,y=(P+KEY)%n+1;fa=LCA(x,y);
        if(IN[x]>IN[y]) swap(x,y);
        if(fa==x) W[++K]=(xcw){IN[x],IN[y],0,K};
        else W[++K]=(xcw){OUT[x],IN[y],fa,K};
    }
    sort(W+1,W+1+K);
    for(int i=1,L=1,R=0;i<=K;i++){
        while(L<W[i].L) Chg(ID[L++]);
        while(L>W[i].L) Chg(ID[--L]);
        while(R<W[i].R) Chg(ID[++R]);
        while(R>W[i].R) Chg(ID[R--]);
        if(W[i].fa) Chg(W[i].fa);
        Ans[W[i].id]=NowAns;
        if(W[i].fa) Chg(W[i].fa);
    }
    int pre=0;
    for(int i=1;i<=K;i+=2){
        printf("%lld\n",Ans[i+(pre&1)]);
        pre=Ans[i+(pre&1)];
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部