权值线段树套区间线段树
把插入的值离散化一下开个线段树
蓝后每个节点开个线段树，维护一下每个数出现的区间和次数
为了防止MLE动态开点就好辣
重点是标记永久化，就是不下传标记，而是每次询问时算上路径上的标记
标记永久化后快了1倍
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define rint register int using namespace std; typedef long long ll; inline int Min(int a,int b){return a<b?a:b;} inline int Max(int a,int b){return a>b?a:b;} void gi(int &x){ static char c=getchar();x=0; while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar(); } void gll(ll &x){ static char c=getchar();x=0; bool f=1; while(c<'0'||c>'9') f=f&&(c!='-'),c=getchar(); while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar(); x=f?x:-x; } #define N 50005 #define W 20000005 int n,m,u,tn,opt[N],L[N],R[N],b[N],rt[200005],lc[W],rc[W],add[W]; ll k[N],sum[W]; #define mid (l+r)/2 void Add(int &o,int l,int r,int x1,int x2){ if(!o) o=++u; sum[o]+=Max(Min(x2,r)-Max(x1,l)+1,0);//遍历过程中先处理掉sum if(x1<=l&&r<=x2){++add[o]; return ;}//标记永久化 if(x1<=mid) Add(lc[o],l,mid,x1,x2); if(x2>mid) Add(rc[o],mid+1,r,x1,x2); } ll Ask(int o,int l,int r,int x1,int x2,ll t){ if(!o) return t*Max(Min(x2,r)-Max(x1,l)+1,0);//注意不返回0 if(x1<=l&&r<=x2) return sum[o]+t*(r-l+1); ll re=0; if(x1<=mid) re+=Ask(lc[o],l,mid,x1,x2,t+add[o]);//累加路径上的标记 if(x2>mid) re+=Ask(rc[o],mid+1,r,x1,x2,t+add[o]); return re; } void ins(int o,int l,int r,int x1,int x2,int v){ Add(rt[o],1,n,x1,x2); if(l==r) return ; if(v<=mid) ins(o<<1,l,mid,x1,x2,v); else ins(o<<1|1,mid+1,r,x1,x2,v); } int ask(int o,int l,int r,int x1,int x2,ll v){ if(l==r) return b[l]; ll tmp=Ask(rt[o<<1|1],1,n,x1,x2,0); if(v<=tmp) return ask(o<<1|1,mid+1,r,x1,x2,v); else return ask(o<<1,l,mid,x1,x2,v-tmp); } int main(){ gi(n);gi(m); for(rint i=1;i<=m;++i){ gi(opt[i]);gi(L[i]);gi(R[i]);gll(k[i]); if(opt[i]==1) b[++tn]=k[i]; }sort(b+1,b+tn+1); tn=unique(b+1,b+tn+1)-b-1;//离散化 for(rint i=1;i<=m;++i) if(opt[i]==1) k[i]=lower_bound(b+1,b+tn+1,k[i])-b; for(rint i=1;i<=m;++i){ if(opt[i]==1) ins(1,1,tn,L[i],R[i],k[i]); else printf("%d ",ask(1,1,tn,L[i],R[i],k[i])); }return 0; }