Vexoben
Jul 2, 2018
题目链接: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大的数是多少。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint
题解
一个直观的想法是线段树套线段树，外层维护区间，内层维护权值。但这时我们会发现外层线段树修改时涉及到懒标记处理，在树套树时很难处理。
那么我们把他反过来。外层维护权值，内层维护区间。这样每次修改时对外层线段树来说就是单点修改，暴力修改涉及到的全部O(logn)个节点即可。内层就是一个区间加。
询问时，首先二分一个答案mid，直接查询大于等于mid的数的个数即可。
内层线段树尝试打了标记永久化。
#include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
const int N=3e5+10;
int ql,qr,c,n,m;
namespace T2 {
int tot=0,ch[N*40][2];
uint tree[N*40],tag[N*40];
void Updata(int &x,int l,int r) {
if (!x) x=++tot;
tree[x]+=min(qr,r)-max(ql,l)+1;
if (ql<=l&&r<=qr) {
tag[x]++; return;
}
int mid=(l+r)>>1;
if (mid>=ql) Updata(ch[x][0],l,mid);
if (mid<qr) Updata(ch[x][1],mid+1,r);
}
uint Query(int x,int l,int r,uint add) {
if (ql<=l&&r<=qr) return tree[x]+add*(r-l+1);
uint ans=0,mid=(l+r)>>1;
if (mid>=ql) ans+=Query(ch[x][0],l,mid,add+tag[x]);
if (mid<qr) ans+=Query(ch[x][1],mid+1,r,add+tag[x]);
return ans;
}
}
namespace T1 {
int rt[N];
void Updata(uint x,int l,int r,int pos) {
T2::Updata(rt[x],1,n);
if (l==r) return;
int mid=(l+r)>>1;
if (mid>=pos) Updata(x<<1,l,mid,pos);
else Updata(x<<1|1,mid+1,r,pos);
}
uint Query(int x,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return T2::Query(rt[x],1,n,0);
uint mid=(l+r)>>1,ans=0;
if (mid>=ql) ans+=Query(x<<1,l,mid,ql,qr);
if (mid<qr) ans+=Query(x<<1|1,mid+1,r,ql,qr);
return ans;
}
}
int main() {
scanf("%d%d",&n,&m);
while (m--) {
int t; scanf("%d%d%d%d",&t,&ql,&qr,&c);
if (t==1) {
T1::Updata(1,1,n*2,c+n);
}
else if (t==2) {
int l=0,r=2*n;
while (l<r) {
int mid=(l+r+1)>>1;
uint num=T1::Query(1,1,2*n,mid,2*n);
if (num<c) r=mid-1;
else l=mid;
}
printf("%d\n",l-n);
}
}
return 0;
}