题目链接:
https://www.lydsy.com/JudgeOnline/problem.php?id=3110
题目:
有N个位置,M个操作。操作有两种,每次操作如果是:
-
1 a b c
:表示在第a个位置到第b个位置,每个位置加上一个数c -
2 a b c
:表示询问从第a个位置到第b个位置,第C大的数是多少。
题解:
注意每一个位置加上一个数并不是数字的加,而是在这个位置上多放一个数
重新捡起OI的我现在还只会线段树套线段树的做法
考虑权值线段树套区间线段树,对于每一段权值区间维护一棵区间线段树,线段树的每一个点代表在该区间内当前权值所有的元素出现的次数
输出答案的时候二分查找
蛮好维护的不是吗?注意要动态开点,顺便把加入的数给离散化一下
代码:
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int N=5e4+15; int n,m,tot,cnt; int root[N<<2]; ll a[N]; struct E { int op,a,b; ll c; }e[N]; struct Tree { int l,r,lazy;ll s; }t[N*400]; inline ll read() { char ch=getchar();ll s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void pushdown(int o,int l,int r) { if (!t[o].lazy||l==r) return; int mid=l+r>>1; int d=t[o].lazy;t[o].lazy=0; if (!t[o].l) t[o].l=++cnt; if (!t[o].r) t[o].r=++cnt; t[t[o].l].lazy+=d; t[t[o].l].s+=(mid-l+1)*d; t[t[o].r].lazy+=d; t[t[o].r].s+=(r-mid)*d; } void pushup(int o) { t[o].s=t[t[o].l].s+t[t[o].r].s; } void ins2(int &o,int l,int r,int x,int y) { if (!o) o=++cnt; if (l>=x&&r<=y) { t[o].s+=r-l+1; t[o].lazy++; return; } pushdown(o,l,r); int mid=l+r>>1; if (x<=mid) ins2(t[o].l,l,mid,x,y); if (y>mid) ins2(t[o].r,mid+1,r,x,y); pushup(o); } void ins1(int o,int l,int r,int x,int y,int z)//对每一个包含添加的数的区间在x~y的值都加1 { ins2(root[o],1,n,x,y); if (l==r) return; int mid=l+r>>1; if (z<=mid) ins1(o<<1,l,mid,x,y,z); else ins1(o<<1|1,mid+1,r,x,y,z); } ll qsum(int o,int l,int r,int x,int y) { if (!o) return 0; if (l>=x&&r<=y) return t[o].s; pushdown(o,l,r); int mid=l+r>>1;ll re=0; if (x<=mid) re+=qsum(t[o].l,l,mid,x,y); if (y>mid) re+=qsum(t[o].r,mid+1,r,x,y); return re; } int query(int o,int l,int r,int a,int b,int c) { if (l==r) return l; int mid=l+r>>1; ll sz=qsum(root[o<<1|1],1,n,a,b); if (sz>=c) return query(o<<1|1,mid+1,r,a,b,c); else return query(o<<1,l,mid,a,b,c-sz); } int main() { n=read();m=read(); for (int i=1;i<=m;i++) { e[i].op=read(); e[i].a=read();e[i].b=read();e[i].c=read(); if (e[i].op==1) a[++tot]=e[i].c; } sort(a+1,a+1+tot); tot=unique(a+1,a+1+tot)-a-1; for (int i=1;i<=m;i++) if (e[i].op==1) e[i].c=lower_bound(a+1,a+1+tot,e[i].c)-a; for (int i=1;i<=m;i++) { if (e[i].op==1) ins1(1,1,tot,e[i].a,e[i].b,e[i].c); if (e[i].op==2) printf("%lld\n",a[query(1,1,tot,e[i].a,e[i].b,e[i].c)]); } return 0; }