题意
分析
自己的想法
可以莫队+平衡树。
对每个颜色维护一颗平衡树，然后移动莫队端点的时候在平衡树中查询。
区间加操作容易实现。
单点修改转化为平衡树的插入删除。
感谢Z前辈的指导。
时间复杂度\(O(n^{\frac{5}{3}} \cdot \log n)\)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
template<class T>T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return x=data*w;
}
typedef long long ll;
using namespace std;
const int MAXN=1e5+7,mod=998244353;
int n,m;
int blo,bl[MAXN]; // block,belong
int c[MAXN],pre[MAXN],now[MAXN]; // color,撤销操作3用的链表
queue<int>pool; // 内存池
int root[MAXN],sz;
struct Treap
{
int ch[MAXN][2],siz[MAXN];
int pos[MAXN],pri[MAXN]; // 在原序列中的位置，优先级
int val[MAXN],sumv[MAXN],addv[MAXN]; // 值，子树的值和，加法标记
int newnode(int p,int v) // 新建位置为p，值为v的节点
{
int nd;
if(!pool.empty())
{
nd=pool.front();
pool.pop();
}
else
{
nd=++sz;
}
ch[nd][0]=ch[nd][1]=0,siz[nd]=1;
pos[nd]=p,pri[nd]=rand()|rand()<<15;
val[nd]=v,sumv[nd]=v,addv[nd]=0;
return nd;
}
void pushup(int now)
{
// cerr<<"pushup "<<now<<endl;
siz[now]=siz[ch[now][0]]+1+siz[ch[now][1]]; // edit 2
sumv[now]=((ll)sumv[ch[now][0]]+val[now]+sumv[ch[now][1]])%mod;
}
void pushdown(int now)
{
// cerr<<"pushdown "<<now<<endl;
if(addv[now])
{
if(ch[now][0]) // 判断非空
{
(val[ch[now][0]]+=addv[now])%=mod,
(sumv[ch[now][0]]+=(ll)siz[ch[now][0]]*addv[now]%mod)%=mod,
(addv[ch[now][0]]+=addv[now])%=mod;
}
if(ch[now][1])
{
(val[ch[now][1]]+=addv[now])%=mod,
(sumv[ch[now][1]]+=(ll)siz[ch[now][1]]*addv[now]%mod)%=mod,
(addv[ch[now][1]]+=addv[now])%=mod;
}
addv[now]=0;
}
}
void split(int&now,int p,int&x,int&y) // 将now所代表的子树位置大于等于p的分到y，其余的分到x
{
// cerr<<"spliting "<<now<<" "<<p<<endl;
if(!now)
{
x=y=0;
return;
}
pushdown(now);
if(pos[now]>=p)
{
// cerr<<"right"<<endl;
y=now;
split(ch[y][0],p,x,ch[y][0]); // edit 1
pushup(y);
}
else
{
// cerr<<"left"<<endl;
x=now;
split(ch[x][1],p,ch[x][1],y);
pushup(x);
}
}
int merge(int x,int y) // 合并x子树和y子树，满足x子树中的每一个节点的位置大于y子树中的每一个节点的位置
{
// cerr<<"merging "<<x<<" "<<y<<endl;
if(!x||!y)
{
return x+y;
}
int now;
if(pri[x]<pri[y])
{
pushdown(x);
now=x;
ch[now][1]=merge(ch[x][1],y);
}
else
{
pushdown(y);
now=y;
ch[now][0]=merge(x,ch[y][0]);
}
pushup(now);
return now;
}
void ins(int&now,int p,int v) // 插入
{
int x,y;
split(now,p,x,y);
now=merge(x,merge(newnode(p,v),y));
}
int del(int &now,int p) // 删除，返回被删的子树（其实就是节点）
{
int x,y,z;
split(now,p,x,y);
split(y,p+1,y,z);
now=merge(x,z);
return y;
}
void add(int&now,int l,int r,int v) // 区间加
{
int x,y,z;
split(now,l,x,y);
split(y,r+1,y,z);
if(y) // edit 3:非空才加
{
(val[y]+=v)%=mod,
(sumv[y]+=(ll)siz[y]*v%mod)%=mod,
(addv[y]+=v)%=mod;
}
now=merge(x,merge(y,z));
}
int qsum(int&now,int p) // 子树（其实就是节点）求和
{
int x,y,z;
split(now,p,x,y);
split(y,p+1,y,z);
int ans=sumv[y]; // y一定存在
now=merge(x,merge(y,z));
// cerr<<"qsum "<<now<<" "<<p<<" ans="<<ans<<endl;
return ans;
}
int qnum(int&now,int l,int r) // 子树中位置在区间[l,r]中的节点的个数
{
int x,y,z;
split(now,l,x,y);
split(y,r+1,y,z);
int ans=siz[y];
now=merge(x,merge(y,z));
// cerr<<"qnum "<<now<<" "<<l<<" "<<r<<" ans="<<y<<" siz="<<siz[y]<<endl;
return ans;
}
}T;
struct Add // 区间加以及单点修改操作
{
int opt;
int t,l,r,x,y;
}A[MAXN];
int a;
struct Quiz // 查询操作
{
int t,id,l,r;
bool operator<(const Quiz&rhs)const
{
return bl[l]^bl[rhs.l]?l<rhs.l:(bl[r]<bl[rhs.r]?r<rhs.r:t<rhs.t);
}
}Q[MAXN];
int ans[MAXN],q;
int qt,ql,qr,sum;
void addAdd(int rk) // 加上A[rk]
{
// cerr<<"addAdd "<<rk<<endl;
if(A[rk].opt==1) // 区间加
{
if(ql<=A[rk].r&&A[rk].l<=qr) // 修改区间与莫队区间有交
(sum+=(ll)T.qnum(root[A[rk].x],max(ql,A[rk].l),min(qr,A[rk].r))*A[rk].y%mod)%=mod;
T.add(root[A[rk].x],A[rk].l,A[rk].r,A[rk].y);
}
else // 单点修改
{
int nd=T.del(root[c[A[rk].x]],A[rk].x);
c[A[rk].x]=A[rk].y;
T.ins(root[A[rk].y],A[rk].x,T.val[nd]);
pool.push(nd);
}
}
void delAdd(int rk) // 减去A[rk]
{
// cerr<<"delAdd "<<rk<<endl;
if(A[rk].opt==1)
{
if(ql<=A[rk].r&&A[rk].l<=qr)
(sum+=mod-(ll)T.qnum(root[A[rk].x],max(ql,A[rk].l),min(qr,A[rk].r))*A[rk].y%mod)%=mod;
T.add(root[A[rk].x],A[rk].l,A[rk].r,mod-A[rk].y);
}
else
{
int nd=T.del(root[c[A[rk].x]],A[rk].x);
c[A[rk].x]=pre[rk];
T.ins(root[pre[rk]],A[rk].x,T.val[nd]);
pool.push(nd);
}
}
void addQuiz(int p) // 莫队区间加上点
{
// cerr<<"addQuiz "<<p<<endl;
(sum+=T.qsum(root[c[p]],p))%=mod;
}
void delQuiz(int p) // 莫队区间减去点
{
// cerr<<"delQuiz "<<p<<endl;
(sum+=mod-T.qsum(root[c[p]],p))%=mod;
}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
srand(20030506);
int n,m;
read(n),read(m);
blo=pow(n,2.0/3);
for(int i=1;i<=n;++i)
{
bl[i]=(i-1)/blo+1;
}
for(int i=1;i<=n;++i)
{
now[i]=read(c[i]);
T.ins(root[c[i]],i,0);
}
for(int i=1;i<=m;++i)
{
int opt;
read(opt);
if(opt==1)
{
A[++a].opt=1,A[a].t=i;
read(A[a].l),read(A[a].r),read(A[a].x),read(A[a].y);
}
else if(opt==2)
{
Q[++q].t=i,Q[q].id=q;
read(Q[q].l),read(Q[q].r);
}
else if(opt==3)
{
A[++a].opt=3,A[a].t=i;
read(A[a].x),read(A[a].y);
pre[a]=now[A[a].x];
now[A[a].x]=A[a].y;
}
}
A[++a].t=1e9;
sort(Q+1,Q+q+1);
qt=0,ql=1,qr=0,sum=0;
for(int i=1;i<=q;++i)
{
while(A[qt+1].t<=Q[i].t)
{
addAdd(++qt);
}
while(A[qt].t>Q[i].t)
{
delAdd(qt--);
}
while(qr<Q[i].r)
{
addQuiz(++qr);
}
while(qr>Q[i].r)
{
delQuiz(qr--);
}
while(ql>Q[i].l)
{
addQuiz(--ql);
}
while(ql<Q[i].l)
{
delQuiz(ql++);
}
ans[Q[i].id]=sum;
}
for(int i=1;i<=q;++i)
{
printf("%d\n",ans[i]);
}
return 0;
}
/*
10 10
1 9 9 2 9 4 1 2 6 9
3 10 10
2 7 9
1 8 9 2 8
1 2 2 3 7
2 3 6
3 8 8
1 2 4 3 1
1 2 10 1 9
2 7 10
2 1 10
*/W学霸的做法
直接分块，对每个颜色维护。
代码清晰易懂，并且跑得飞快。
时间复杂度\(O(n \sqrt{n})\)
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#include<cassert>
#define rg register
#define il inline
#define co const
#pragma GCC optimize ("O0")
using namespace std;
template<class T> il T read()
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return data*w;
}
template<class T> il T read(T&x)
{
return x=read<T>();
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=1e5+7,mod=998244353;
int n,m,len;
int bl[MAXN],c[MAXN],a[MAXN];
int cnt[350][MAXN];
int laz[350][MAXN];
int ans[350];
int mul(int x,int y)
{
return (ll)x*y%mod;
}
int add(int x,int y)
{
return (x+y)%mod;
}
int pul(int x,int y)
{
return (x+mod-y)%mod;
}
void change(int l,int r,int x,int y)
{
if(bl[l]!=bl[r])
{
for(int i=bl[l]+1;i<bl[r];++i)
{
laz[i][x]=add(laz[i][x],y);
ans[i]=add(ans[i],mul(cnt[i][x],y));
}
for(int i=l;i<=bl[l]*len;++i)
if(c[i]==x)
{
ans[bl[i]]=add(ans[bl[i]],y);
a[i]=add(a[i],y);
}
for(int i=(bl[r]-1)*len+1;i<=r;++i)
if(c[i]==x)
{
ans[bl[i]]=add(ans[bl[i]],y);
a[i]=add(a[i],y);
}
}
else
{
for(int i=l;i<=r;++i)
if(c[i]==x)
{
ans[bl[i]]=add(ans[bl[i]],y);
a[i]=add(a[i],y);
}
}
}
int query(int l,int r)
{
int res=0;
if(bl[l]!=bl[r])
{
for(int i=bl[l]+1;i<bl[r];++i)
{
res=add(res,ans[i]);
}
for(int i=l;i<=bl[l]*len;++i)
{
res=add(res,add(a[i],laz[bl[i]][c[i]]));
}
for(int i=(bl[r]-1)*len+1;i<=r;++i)
{
res=add(res,add(a[i],laz[bl[i]][c[i]]));
}
}
else
{
for(int i=l;i<=r;++i)
{
res=add(res,add(a[i],laz[bl[i]][c[i]]));
}
}
return res;
}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
read(n);read(m);
len=sqrt(n);
for(int i=1;i<=n;++i)
{
bl[i]=(i-1)/len+1;
read(c[i]);
++cnt[bl[i]][c[i]];
}
int opt,l,r,x,y;
for(int i=1;i<=m;++i)
{
read(opt);
if(opt==1)
{
read(l);read(r);read(x);read(y);
change(l,r,x,y);
}
else if(opt==2)
{
read(l);read(r);
printf("%d\n",query(l,r));
}
else
{
read(x);read(y);
if(c[x]==y)
continue;
--cnt[bl[x]][c[x]];
a[x]=add(a[x],laz[bl[x]][c[x]]);
if(!cnt[bl[x]][c[x]])
laz[bl[x]][c[x]]=0;
c[x]=y;
a[x]=pul(a[x],laz[bl[x]][c[x]]);
++cnt[bl[x]][c[x]];
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}标解
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define fi first
#define se second
#define MP make_pair
int read()
{
int v = 0, f = 1;
char c = getchar();
while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
return v * f;
}
const int N = 300010;
const ll MOD = 998244353;
int n, q, B, B2;
int c[N], L[N], R[N], belong[N], d[N], now[N], mx[N], op[N][10], _c[N];
ll a[N], f[N], num[600][600], g[600][600];
set<int> S[N];
int main()
{
freopen("color.in", "r", stdin);
freopen("color.out", "w", stdout);
n = read(), q = read();
for (int i = 1; i <= n; i++)
{
c[i] = _c[i] = read();
S[c[i]].insert(i);
now[c[i]]++;
}
for (int i = 1; i <= n; i++)
mx[i] = now[i];
for (int i = 1; i <= q; i++)
{
op[i][0] = read();
if (op[i][0] == 1)
{
op[i][1] = read();
op[i][2] = read();
op[i][3] = read();
op[i][4] = read();
}
if (op[i][0] == 2)
{
op[i][1] = read();
op[i][2] = read();
}
if (op[i][0] == 3)
{
op[i][1] = read();
op[i][2] = read();
now[_c[op[i][1]]]--;
_c[op[i][1]] = op[i][2];
now[op[i][2]]++;
mx[op[i][2]] = max(mx[op[i][2]], now[op[i][2]]);
}
}
B2 = sqrt(n + q + 0.5);
int cnt = 0;
for (int i = 1; i <= n; i++)
if (mx[i] > B2)
d[i] = ++cnt;
B = sqrt(n + 0.5) + 2;
for (int i = 1; i <= B; i++)
{
L[i] = (i - 1) * B + 1;
R[i] = i * B;
for (int j = L[i]; j <= R[i]; j++)
{
belong[j] = i;
if (d[c[j]])
num[i][d[c[j]]]++;
}
}
for (int j = 1; j <= q; j++)
{
if (op[j][0] == 1)
{
int l = op[j][1], r = op[j][2], x = op[j][3];
ll y = op[j][4];
if (d[x])
{
if (belong[l] == belong[r])
{
for (int i = l; i <= r; i++)
if (c[i] == x)
{
a[i] = (a[i] + y) % MOD;
f[belong[i]] = (f[belong[i]] + y) % MOD;
}
} else
{
for (int i = l; i <= R[belong[l]]; i++)
if (c[i] == x)
{
a[i] = (a[i] + y) % MOD;
f[belong[i]] = (f[belong[i]] + y) % MOD;
}
for (int i = belong[l] + 1; i <= belong[r] - 1; i++)
{
g[i][d[x]] = (g[i][d[x]] + y) % MOD;
f[i] = (f[i] + num[i][d[x]] * y) % MOD;
}
for (int i = L[belong[r]]; i <= r; i++)
if (c[i] == x)
{
a[i] = (a[i] + y) % MOD;
f[belong[i]] = (f[belong[i]] + y) % MOD;
}
}
} else
{
for (set<int> :: iterator i = S[x].begin(); i != S[x].end(); i++)
{
int u = *i;
if (l <= u && u <= r)
{
a[u] = (a[u] + y) % MOD;
f[belong[u]] = (f[belong[u]] + y) % MOD;
}
}
}
}
if (op[j][0] == 2)
{
int l = op[j][1], r = op[j][2];
ll ans = 0;
if (belong[l] == belong[r])
{
for (int i = l; i <= r; i++)
if (d[c[i]])
ans = (ans + g[belong[i]][d[c[i]]] + a[i]) % MOD;
else
ans = (ans + a[i]) % MOD;
} else
{
for (int i = l; i <= R[belong[l]]; i++)
if (d[c[i]])
ans = (ans + g[belong[i]][d[c[i]]] + a[i]) % MOD;
else
ans = (ans + a[i]) % MOD;
for (int i = belong[l] + 1; i <= belong[r] - 1; i++)
ans = (ans + f[i]) % MOD;
for (int i = L[belong[r]]; i <= r; i++)
if (d[c[i]])
ans = (ans + g[belong[i]][d[c[i]]] + a[i]) % MOD;
else
ans = (ans + a[i]) % MOD;
}
printf("%lld\n", ans);
}
if (op[j][0] == 3)
{
int x = op[j][1], y = op[j][2];
if (d[c[x]])
{
a[x] = (a[x] + g[belong[x]][d[c[x]]]) % MOD;
num[belong[x]][d[c[x]]]--;
}
S[c[x]].erase(x);
c[x] = y;
S[c[x]].insert(x);
if (d[c[x]])
{
a[x] = (a[x] - g[belong[x]][d[c[x]]] + MOD) % MOD;
num[belong[x]][d[c[x]]]++;
}
}
}
}