Bzoj3110 [Zjoi2013]K大数查询 [整体二分]

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 7596 Solved: 2365

Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

Input

第一行N，M
接下来M行，每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

HINT

【样例说明】

第一个操作后位置 1 的数只有 1 ，位置 2 的数也只有 1 。第二个操作后位置 1

的数有 1 、 2 ，位置 2 的数也有 1 、 2 。第三次询问位置 1 到位置 1 第 2 大的数是

1 。第四次询问位置 1 到位置 1 第 1 大的数是 2 。第五次询问位置 1 到位置 2 第 3

大的数是 1 。‍

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=Maxlongint

Source

整体二分 (+CDQ分治?)

二分答案，依次判断每一个询问，把答案大于当前钦定值的划成一部分，把答案小于当前钦定值的划进另一部分。

由于既有修改也有查询，所以需要确保操作符合时间顺序，从R倒序扩大操作区间后，需要reverse

注意求的是第K大，区间的划分方向和求第K小是反的

WA了三四次才注意到数据会爆int……

　　之后翻到很久以前写的树套树解法，那篇博客里清楚地写道：

　　数据会爆int，坑

蛤蛤蛤sx博主不长记性活该WA一串

附树套树解法：http://www.cnblogs.com/SilverNebula/p/6358388.html

  1 /*by SilverN*/
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 #define LL long long
  9 using namespace std;
 10 const int mxn=100010;
 11 int read(){
 12     int x=0,f=1;char ch=getchar();
 13     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 int n,m;
 18 struct node{LL smm,mk;}t[mxn<<2];
 19 void PD(int l,int r,int rt){
 20         int lc=rt<<1,rc=rt<<1|1;int mid=(l+r)>>1;
 21         t[lc].smm+=t[rt].mk*(mid-l+1);t[rc].smm+=t[rt].mk*(r-mid);
 22         t[lc].mk+=t[rt].mk; t[rc].mk+=t[rt].mk;
 23         t[rt].mk=0;
 24     return;
 25 }
 26 void update(int L,int R,LL v,int l,int r,int rt){
 27     if(t[rt].mk)PD(l,r,rt);
 28     if(L<=l && r<=R){
 29         t[rt].smm+=(LL)v*(r-l+1);
 30         t[rt].mk+=v;
 31         return;
 32     }
 33     int mid=(l+r)>>1;
 34     if(L<=mid)update(L,R,v,l,mid,rt<<1);
 35     if(R>mid)update(L,R,v,mid+1,r,rt<<1|1);
 36     t[rt].smm=t[rt<<1].smm+t[rt<<1|1].smm;
 37     return;
 38 }
 39 LL query(int L,int R,int l,int r,int rt){
 40     if(L<=l && r<=R){return t[rt].smm;}
 41     if(t[rt].mk)PD(l,r,rt);
 42     int mid=(l+r)>>1;
 43     LL res=0;
 44     if(L<=mid)res+=query(L,R,l,mid,rt<<1);
 45     if(R>mid)res+=query(L,R,mid+1,r,rt<<1|1);
 46     return res;
 47 }
 48  
 49 //
 50 struct que{
 51     int a,b,c;
 52     bool tp;
 53     int res;
 54     int id;
 55 }q[mxn];
 56 int now[mxn],tmp[mxn];
 57 int ans[mxn];
 58 void solve(int l,int r,int L,int R){//答案区间 询问区间 
 59     if(l>r || L>R)return;
 60     int mid=(l+r)>>1;
 61     int dl=L-1,dr=R+1;
 62     for(int i=L;i<=R;i++){
 63         int x=now[i];
 64         if(q[x].tp==1){//添加 
 65             if(q[x].c>mid){
 66                 update(q[x].a,q[x].b,1,1,n,1);
 67                 tmp[--dr]=now[i];
 68             }
 69             else{
 70                 tmp[++dl]=now[i];
 71             }
 72         }
 73         else{//查询 
 74             LL res=query(q[x].a,q[x].b,1,n,1);//记得开long long呀 
 75             if(res<q[x].c){
 76                 q[x].c-=res;
 77                 ans[q[x].id]=q[x].res=mid;
 78                 tmp[++dl]=now[i];
 79             }
 80             else{
 81                 tmp[--dr]=now[i];
 82             }
 83         }
 84     }
 85     reverse(tmp+dr,tmp+R+1);
 86     for(int i=L;i<=R;i++){
 87         now[i]=tmp[i];
 88         int x=now[i];
 89         if(q[x].tp==1 && q[x].c>mid){
 90             update(q[x].a,q[x].b,-1,1,n,1);
 91         }
 92     }
 93     solve(l,mid-1,L,dl);
 94     solve(mid+1,r,dl+1,R);
 95     return;
 96 }
 97 int main(){
 98     int i,j;
 99     n=read();m=read();
100     for(i=1;i<=m;i++){
101         j=read();
102         if(j==1)q[i].tp=1;
103             else q[i].tp=0;// 添加/查询 
104         q[i].a=read();q[i].b=read();q[i].c=read();
105         q[i].id=i;
106     }
107     for(i=1;i<=m;i++)now[i]=i;
108     solve(1,n,1,m);
109     for(i=1;i<=m;i++){
110         if(!q[i].tp)
111             printf("%d
",ans[i]);
112     }
113     return 0;
114 }