1A啊，激动。
首先，不修改的情况下可以直接用主席树搞，修改的话，直接用主席树搞一次修改的情况下复杂度是O(nlogn)的。
就像你要求区间和一样，用前缀和查询是O(1),修改是O(n),只不过主席树是前缀和套权值线段树，每个操作乘个logn。
如果用树状数组来维护区间和，查询是O(logn),修改是O(logn),那么用树状数组套权值线段树，每个操作就是O(log^2n).
由于这道题还需要修改 改动一个数的前驱和后继。用set搞一搞。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi 3.1415926535 # define eps 1e-9 # define MOD 1000000009 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int res=0, flag=0; char ch; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+(ch-'0'); return flag?-res:res; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=10005; //Code begin... struct Node{int l, r; bool flag;}node[N]; int a[N], vis[N<<1], to[N], sz, n; int root[N], ls[N*200], rs[N*200], s[N*200]; VI v; set<int>mt[N<<1]; set<int>::iterator it; void update(int l, int r, int x, int &y, int z, int val){ y=++sz; s[y]=s[x]+val; if (l==r) return ; ls[y]=ls[x]; rs[y]=rs[x]; int mid=(l+r)>>1; if (z<=mid) update(l,mid,ls[x],ls[y],z,val); else update(mid+1,r,rs[x],rs[y],z,val); } int query(int l, int r, int x, int L){ if (r<L) return 0; if (l>=L) return s[x]; int mid=(l+r)>>1; return query(l,mid,ls[x],L)+query(mid+1,r,rs[x],L); } void add(int x, int y, int val){ for (int i=x; i<=n; i+=lowbit(i)) update(1,n+1,root[i],root[i],y,val); } int sum(int x, int val){ int res=0; for (int i=x; i; i-=lowbit(i)) res+=query(1,n+1,root[i],val); return res; } int main () { int m, tmp; char flag[3]; scanf("%d%d",&n,&m); FOR(i,1,n) scanf("%d",a+i), v.pb(a[i]); FOR(i,1,m) { scanf("%s%d%d",flag,&node[i].l,&node[i].r); if (flag[0]=='Q') node[i].flag=true; else v.pb(node[i].r); } sort(v.begin(),v.end()); int siz=unique(v.begin(),v.end())-v.begin(); FOR(i,1,n) { a[i]=lower_bound(v.begin(),v.begin()+siz,a[i])-v.begin()+1; if (vis[a[i]]) to[vis[a[i]]]=i; vis[a[i]]=i; mt[a[i]].insert(i); } FOR(i,1,n) if (!to[i]) to[i]=n+1; FOR(i,1,n) add(i,to[i],1); FOR(i,1,m) { if (node[i].flag) printf("%d ",sum(node[i].r,node[i].r+1)-sum(node[i].l-1,node[i].r+1)); else { node[i].r=lower_bound(v.begin(),v.begin()+siz,node[i].r)-v.begin()+1; it=mt[a[node[i].l]].lower_bound(node[i].l); ++it; if (it==mt[a[node[i].l]].end()) tmp=n+1; else tmp=*it; add(node[i].l,tmp,-1); --it; if (it!=mt[a[node[i].l]].begin()) --it, add(*it,node[i].l,-1), add(*it,tmp,1); mt[a[node[i].l]].erase(node[i].l); a[node[i].l]=node[i].r; it=mt[node[i].r].lower_bound(node[i].l); if (it==mt[node[i].r].end()) tmp=n+1; else tmp=*it; add(node[i].l,tmp,1); if (it!=mt[node[i].r].begin()) --it, add(*it,tmp,-1), add(*it,node[i].l,1); mt[node[i].r].insert(node[i].l); } } return 0; }