注意到等级的变化最多有nm次。于是考虑比较暴力的做法，线段树维护每个区间内每个等级角色的最大经验值，区间加时看有没有可以升级的，如果有则暴力向两边递归，否则打上标记。复杂度O(nmlogn)。
似乎有更优的做法。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<cassert> using namespace std; #define N 1000010 #define int long long #define inf 1000000000000000 int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,q,a[12],v[N]; struct data{int L,R,lazy,sum,max[12]; }tree[N<<2]; int value(int x) { for (int i=1;i<=m;i++) if (a[i]>x) return i-1; } void up(int k) { for (int i=1;i<=m;i++) tree[k].max[i]=max(tree[k<<1].max[i],tree[k<<1|1].max[i]); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } void update(int k,int x) { if (tree[k].L==tree[k].R) { for (int i=1;i<=m;i++) if (tree[k].max[i]>=0) {x+=tree[k].max[i];tree[k].max[i]=-inf;break;} tree[k].max[(tree[k].sum=value(x))+1]=x; return; } for (int i=1;i<=m;i++) { tree[k].max[i]+=x; if (tree[k].max[i]>=a[i]) { x+=tree[k].lazy,tree[k].lazy=0; update(k<<1,x), update(k<<1|1,x); up(k); return; } } tree[k].lazy+=x; } void down(int k) { update(k<<1,tree[k].lazy); update(k<<1|1,tree[k].lazy); tree[k].lazy=0; } void build(int k,int l,int r) { tree[k].L=l,tree[k].R=r; for (int i=1;i<=m;i++) tree[k].max[i]=-inf; if (l==r) {tree[k].sum=value(v[l]),tree[k].max[value(v[l])+1]=v[l];return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); } void add(int k,int l,int r,int x) { if (tree[k].L==l&&tree[k].R==r) {update(k,x);return;} if (tree[k].lazy) down(k); int mid=tree[k].L+tree[k].R>>1; if (r<=mid) add(k<<1,l,r,x); else if (l>mid) add(k<<1|1,l,r,x); else add(k<<1,l,mid,x),add(k<<1|1,mid+1,r,x); up(k); } void modify(int k,int p,int x) { if (tree[k].L==tree[k].R) { for (int i=1;i<=m;i++) tree[k].max[i]=-inf; tree[k].max[(tree[k].sum=value(x))+1]=x; return; } if (tree[k].lazy) down(k); int mid=tree[k].L+tree[k].R>>1; if (p<=mid) modify(k<<1,p,x); else modify(k<<1|1,p,x); up(k); } int query(int k,int l,int r) { if (tree[k].L==l&&tree[k].R==r) return tree[k].sum; if (tree[k].lazy) down(k); int mid=tree[k].L+tree[k].R>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); } signed main() { #ifndef ONLINE_JUDGE freopen("c.in","r",stdin); freopen("c.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(),q=read(); for (int i=1;i<=m;i++) a[i]=read();a[++m]=inf; for (int i=1;i<=n;i++) v[i]=read(); build(1,1,n); while (q--) { int op=read(); if (op==1) { int l=read(),r=read(),x=read(); add(1,l,r,x); } if (op==2) { int p=read(),x=read(); modify(1,p,x); } if (op==3) { int l=read(),r=read(); printf("%d ",query(1,l,r)); } } return 0; }