Lvat_s Blog

这题我在学校的OJ上A掉了，在BZOJ上WA了……很神奇

但是还是发一下代码吧，如果有什么错误欢迎各位老司机们指出

是一个树套树，外围像区间K大一样维护一个权值线段树，内部维护一个线段树记录这个值出现在哪些区间上

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,cnt,root[500005];

struct SegTree{
int nl,nr,l,r,sum,tag;
}tree[20000005];

void Pushdown(int rt){
if(tree[rt].tag && tree[rt].l!=tree[rt].r){
	int mid=tree[rt].l+tree[rt].r>>1;
	if(!tree[rt].nl){tree[rt].nl=++cnt;tree[tree[rt].nl].l=tree[rt].l;tree[tree[rt].nl].r=mid;}
	if(!tree[rt].nr){tree[rt].nr=++cnt;tree[tree[rt].nr].l=mid+1;tree[tree[rt].nr].r=tree[rt].r;}
	tree[tree[rt].nl].tag+=tree[rt].tag;
	tree[tree[rt].nr].tag+=tree[rt].tag;
	tree[tree[rt].nl].sum+=(tree[tree[rt].nl].r-tree[tree[rt].nl].l+1)*tree[rt].tag;
	tree[tree[rt].nr].sum+=(tree[tree[rt].nr].r-tree[tree[rt].nr].l+1)*tree[rt].tag;
	tree[rt].tag=0;
}
}

void Pushup(int rt){
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}

void Modify(int &rt,int l,int r,int L,int R){
if(!rt){rt=++cnt;tree[rt].l=l;tree[rt].r=r;}
Pushdown(rt);
if(L<=tree[rt].l && tree[rt].r<=R){
	tree[rt].sum+=tree[rt].r-tree[rt].l+1;
    tree[rt].tag++;
    return;
}
int mid=tree[rt].l+tree[rt].r>>1;
if(L<=mid)Modify(tree[rt].nl,l,mid,L,R);
if(R>mid)Modify(tree[rt].nr,mid+1,r,L,R);
Pushup(rt);
}

int Query(int rt,int l,int r){
if(!rt)return 0;
Pushdown(rt);
if(l<=tree[rt].l && tree[rt].r<=r){return tree[rt].sum;}
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Query(tree[rt].nl,l,r);
if(r>mid)ans+=Query(tree[rt].nr,l,r);
Pushup(rt);
return ans;
}

void Insert(int l,int r,int v){
int L=1,R=n,rt=1;
while(L!=R){
	int mid=L+R>>1;
	Modify(root[rt],1,n,l,r);
	if(v<=mid){R=mid;rt*=2;}
	else {L=mid+1;rt=rt*2+1;}
}
Modify(root[rt],1,n,l,r);
}

int Ask(int l,int r,int k){
int L=1,R=n,rt=1;
while(L!=R){
	int mid=L+R>>1;
	int ans=Query(root[rt*2],l,r);
	if(ans>=k){R=mid;rt*=2;}
	else {L=mid+1;rt=rt*2+1;k-=ans;}
}
return L;
}

int main(){
freopen("3110.in","r",stdin);
freopen("3110.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
    int opt,a,b,c;
    scanf("%d %d %d %d",&opt,&a,&b,&c);
    if(opt==1)Insert(a,b,n-c+1);
    if(opt==2)printf("%d\n",n-Ask(a,b,c)+1);
}
return 0;
}