注意操作 $1$ 是在区间的每个位置加入一个数，不是加上一个值
相当于每个位置维护的是一个集合
显然树套树
一开始想的是区间线段树套权值线段树
发现这样询问区间第 $K$ 大时就要先二分答案再用 $O(log^2_n)$ 时间查询
那么单次询问的复杂度就有 $O(log^3_n)$ ，显然不行
考虑权值线段树套区间线段树
单次插入复杂度还是 $O(log^2_n)$，询问时只要在权值线段树上二分就行
那么单次操作复杂度就是 $O(log^2_n)$
据说此题很卡常，为了防止我的大常数导致 $GG$ 所以学了一下线段树的标记用久化
简单说就是标记不下传，只要询问时把经过节点的标记加进来一起计算贡献，代码不难想
因为空间问题所以内层的区间线段树要动态开点
因为插入的数可能为负，所以要离散化，注意 $long long$ !
#include#include #include #include #include using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}inline ll readll(){ ll x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=2e5+7,M=2e7+7;int n,m,cnt,A[N],T;int rt[N],L[M],R[M],tag[M];//区间线段树的数组，根节点，左儿子，右儿子，永久标记ll sum[M];//区间线段树数组，区间和int ql,qr; ll res;void add(int &o,int l,int r)//区间加1{ if(!o) o=++cnt;//动态开点 sum[o]+= max( min(r,qr)-max(l,ql)+1 ,0) ;//因为永久标记所以要这样更新sum if(l>=ql&&r<=qr) { tag[o]++; return; }//注意我的tag是给儿子的，要先更新sum int mid=l+r>>1; if(ql<=mid) add(L[o],l,mid); if(qr>mid) add(R[o],mid+1,r);}void query(int o,int l,int r,int tot)//区间求和,tot维护当前经过节点的tag的和{ if(l>=ql&&r<=qr) { res+=sum[o]+1ll*(r-l+1)*tot; return; }//更新res int mid=l+r>>1; if(ql<=mid) query(L[o],l,mid,tot+tag[o]); if(qr>mid) query(R[o],mid+1,r,tot+tag[o]);}int POS,RES; ll K;void ADD(int o,int l,int r)//权值线段树插入{ add(rt[o],1,n); if(l==r) return; int mid=l+r>>1; if(POS<=mid) ADD(o<<1,l,mid); else ADD(o<<1|1,mid+1,r);}void QUERY(int o,int l,int r)//权值线段树处理询问{ if(l==r) { RES=A[l]; return; } int mid=l+r>>1; res=0; query(rt[o<<1|1],1,n,0);//注意优先走大的！ if(res