题解 P2464 【[SDOI2008]郁闷的小J】

浅色调 · 2018-11-05 20:24:04 · 题解

Solution：

　　本题解法太多，前后用了4种方法去做，由简入繁。

　　法一：分块+map（736ms）

　　我们可以将数列划分为\sqrt n块，每个块用map维护块内元素出现次数，那么单次修改可以做到O(\log(\sqrt n))，单次查询能做到\sqrt n \log (\sqrt n)。时间复杂度O(n\sqrt n \log(\sqrt n))，极限数据能卡到2e8，但是本题数据比较水也能过。

　　法一代码：

/*Code by 520 -- 10.28*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
using namespace __gnu_pbds;
const int N=100005;
gp_hash_table<int,int>mp[1005];
int n,m,a[N],bl[N],ln[N],rn[N],clo,u,v,w;
char opt[2];

int gi(){
    int a=0;char x=getchar();
    while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return a;
}    

il int query(int x,int y,int z){
    int bx=bl[x],by=bl[y],res=0;
    if(bx==by) {
        For(i,x,y) res+=(a[i]==z);
        return res;
    }
    For(i,bx+1,by-1) res+=mp[i][z];
    For(i,x,rn[bx]) res+=(a[i]==z);
    For(i,ln[by],y) res+=(a[i]==z);
    return res;
}

int main(){
    n=gi(),m=gi(); clo=sqrt(n);
    For(i,1,n) {
        a[i]=gi(),bl[i]=(i-1)/clo+1,mp[bl[i]][a[i]]++;
        if(!ln[bl[i]]) ln[bl[i]]=i;
        rn[bl[i]]=i;
    }
    For(i,1,m){
        scanf("%s",opt);
        if(opt[0]=='Q') u=gi(),v=gi(),w=gi(),printf("%d\n",query(u,v,w));
        else {
            u=gi(),v=gi();
            mp[bl[u]][a[u]]--;
            a[u]=v;
            mp[bl[u]][a[u]]++;
        }
    }
    return 0;
}

　　法二：分块+离散化（383ms）

　　我们显然可以用奇技淫巧优化掉法一中的\log(\sqrt n)。只需要离线操作，并对数的值域离散，然后用空间换时间，一种方法是把块数调小，另一种是直接用short类型来开桶（反正一个块内的元素次数不会超过\sqrt n<2^{16}-1），能卡着空间过。时间复杂度O(n\sqrt n)。

　　法二代码：

/*Code by 520 -- 10.28*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=100005;
int n,m,a[N],bl[N],ln[N],rn[N],clo,u,v,w,*q[N<<1],cnt;
struct node{
    int l,r,x;
}t[N];
short mp[318][N<<1];
char opt[N][2];

int gi(){
    int a=0;char x=getchar();
    while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return a;
}    

il bool cmp(int *a,int *b){return *a<*b;}

il int query(int x,int y,int z){
    int bx=bl[x],by=bl[y],res=0;
    if(bx==by) {
        For(i,x,y) res+=(a[i]==z);
        return res;
    }
    For(i,bx+1,by-1) res+=mp[i][z];
    For(i,x,rn[bx]) res+=(a[i]==z);
    For(i,ln[by],y) res+=(a[i]==z);
    return res;
}

int main(){
    n=gi(),m=gi(); clo=sqrt(n);
    For(i,1,n) {
        a[i]=gi(),q[++cnt]=&a[i],bl[i]=(i-1)/clo+1;
        if(!ln[bl[i]]) ln[bl[i]]=i;
        rn[bl[i]]=i;
    }
    For(i,1,m){
        scanf("%s",opt[i]);
        if(opt[i][0]=='Q') t[i]=node{gi(),gi(),gi()},q[++cnt]=&t[i].x;
        else t[i]=node{gi(),gi(),0},q[++cnt]=&t[i].r;
    }
    sort(q+1,q+cnt+1,cmp); int lst=-1,tot=0;
    For(i,1,cnt) if(*q[i]!=lst) lst=*q[i],*q[i]=++tot; else *q[i]=tot;
    For(i,1,n) mp[bl[i]][a[i]]++;
    For(i,1,m){
        if(opt[i][0]=='Q') printf("%d\n",query(t[i].l,t[i].r,t[i].x));
        else {
            u=t[i].l,v=t[i].r;
            mp[bl[u]][a[u]]--;
            a[u]=v;
            mp[bl[u]][a[u]]++;
        }
    }
    return 0;
}

　　法三：带修改主席树（1156ms ）

　　本题显然是个带修主席树的板子，只需要离线操作并对值域离散，然后就直接板子咯。时间复杂度O(n\log^2 n)。

　　法三代码：

/*Code by 520 -- 10.28*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=100005;
int n,m,a[N],*q[N<<1],cnt,tot,rt[N],X[N],Y[N],tx,ty;
struct query{
    int l,r,x;
}qus[N];
struct node{
    int ls,rs,sz;
}t[N*300];
char opt[N][2];

int gi(){
    int a=0;char x=getchar();
    while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return a;
}    

il bool cmp(int *a,int *b){return *a<*b;}

void ins(int l,int r,int k,int x,int lst,int &rt){
    if(!rt) rt=++tot; t[rt]=t[lst],t[rt].sz+=x;
    if(l==r) return;
    int m=l+r>>1;
    if(k<=m) ins(l,m,k,x,t[lst].ls,t[rt].ls);
    else ins(m+1,r,k,x,t[lst].rs,t[rt].rs);
}

il void update(int i,int v){
    int k=a[i];
    while(i<=n) ins(1,cnt,k,v,rt[i],rt[i]),i+=i&-i;
}

il int calc(int x){
    int l=1,r=cnt,k=qus[x].x,res=0;
    tx=ty=0;
    for(RE int i=qus[x].l-1;i;i-=i&-i) X[++tx]=rt[i];
    for(RE int i=qus[x].r;i;i-=i&-i) Y[++ty]=rt[i];
    while(1){
        int mid=l+r>>1;
        if(l==r) break;
        if(mid>=k) {
            r=mid;
            For(i,1,tx) X[i]=t[X[i]].ls;
            For(i,1,ty) Y[i]=t[Y[i]].ls;
        }
        else {
            l=mid+1;
            For(i,1,tx) X[i]=t[X[i]].rs;
            For(i,1,ty) Y[i]=t[Y[i]].rs;
        }
    }
    For(i,1,ty) res+=t[Y[i]].sz;
    For(i,1,tx) res-=t[X[i]].sz;
    return res;
}

int main(){
    n=gi(),m=gi();
    For(i,1,n) a[i]=gi(),q[++cnt]=&a[i];
    For(i,1,m){
        scanf("%s",opt[i]);
        if(opt[i][0]=='Q') qus[i]=query{gi(),gi(),gi()},q[++cnt]=&qus[i].x;
        else qus[i]=query{gi(),gi(),0},q[++cnt]=&qus[i].r;
    }
    sort(q+1,q+cnt+1,cmp); int lst=-1;
    For(i,1,cnt) if(*q[i]!=lst) lst=*q[i],*q[i]=++tot; else *q[i]=tot;
    cnt=tot;
    memset(&t[tot=0],0,sizeof(t[0]));
    For(i,1,n) update(i,1);
    For(i,1,m){
        if(opt[i][0]=='Q') printf("%d\n",calc(i));
        else {
            int u=qus[i].l,v=qus[i].r;
            update(u,-1),a[u]=v,update(u,1);
        }
    }
    return 0;
}

　　法四：平衡树（432ms）

　　我们离线操作并对值域离散后，可以直接用无旋treap维护每个值域的下标中序，那么修改就是简单的删除操作，查询也是简单的分离操作。时间复杂度O(n\log n)。

　　法四代码：

/*Code by 520 -- 10.28*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=200005;
int n,m,a[N],*q[N<<1],cnt;
int ch[N][2],rt[N],rnd[N],date[N],siz[N];
struct node{
    int l,r,x;
}t[N];
char opt[N][2];

int gi(){
    int a=0;char x=getchar();
    while(x<'0'||x>'9') x=getchar();
    while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return a;
}    

il bool cmp(int *a,int *b){return *a<*b;}

il int newnode(int v){
    ++cnt;
    siz[cnt]=1,date[cnt]=v,rnd[cnt]=rand();
    return cnt;
}

il void up(int rt){siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;}

int merge(int x,int y){
    if(!x||!y) return x+y;
    if(rnd[x]<rnd[y]) {ch[x][1]=merge(ch[x][1],y),up(x);return x;}
    else {ch[y][0]=merge(x,ch[y][0]),up(y);return y;}
}

void split(int rt,int v,int &x,int &y){
    if(!rt) {x=y=0;return;}
    if(date[rt]<=v) x=rt,split(ch[rt][1],v,ch[x][1],y),up(x);
    else y=rt,split(ch[rt][0],v,x,ch[y][0]),up(y);
}

il void ins(int k,int v){
    int x,y; split(rt[k],v,x,y),rt[k]=merge(merge(x,newnode(v)),y);
}

il void del(int k,int v){
    int x,y,z; split(rt[k],v,x,y),split(x,v-1,x,z),rt[k]=merge(x,y);
}

int main(){
    srand(time(0));
    n=gi(),m=gi();
    For(i,1,n) a[i]=gi(),q[++cnt]=&a[i];
    For(i,1,m){
        scanf("%s",opt[i]);
        if(opt[i][0]=='Q') t[i]=node{gi(),gi(),gi()},q[++cnt]=&t[i].x;
        else t[i]=node{gi(),gi(),0},q[++cnt]=&t[i].r;
    }
    sort(q+1,q+cnt+1,cmp); int lst=-1,tot=0;
    For(i,1,cnt) if(*q[i]!=lst) lst=*q[i],*q[i]=++tot; else *q[i]=tot;
    cnt=0;
    For(i,1,n) ins(a[i],i);
    For(i,1,m){
        if(opt[i][0]=='Q') {
            int x,y,z; 
            split(rt[t[i].x],t[i].r,x,y),split(x,t[i].l-1,x,z);
            printf("%d\n",siz[z]);
            rt[t[i].x]=merge(merge(x,z),y);
        }
        else {
            int x,y,z,u=t[i].l,v=t[i].r;
            del(a[u],u),a[u]=v,ins(a[u],u);
        }
    }
    return 0;
}