BZOJ 3110 [Zjoi2013]K大数查询

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

正解：CDQ分治

解题报告：

　　听说这是一道CDQ分治模板题，于是跑来围观。

　　CDQ分治的处理十分神奇，一般用于处理有修改、有查询的可离线的题目。　　

　　这道题目就是每次在一段位置都插入一个数，并动态询问问区间内第几大的数是多少。我们可以考虑CDQ分治。首先二分一个答案x，x指的是询问的答案（题意中说了只能是1到n），我们就对于一下当前这一段的处理序列中，先依次处理，碰到询问就考虑是否可行。如果对于一个询问，发现当前的x之下查询的ans大于那个值，说明答案更小，所以要放到左边去递归处理，但是同时记得，把询问的值减掉查询出的ans，表示这一段肯定比它大，先减掉。至于查询的话，区间修改、区间查询，可以考虑用树状数组。

　　总的来说，我对CDQ分治体会还是挺深，但是还是不够熟练，需要多加练习。

 1 //It is made by jump~
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #include <set>
13 using namespace std;
14 typedef long long LL;
15 const int MAXM = 50011;
16 int n,m;
17 int tmp[MAXM],ans[MAXM];
18 LL c1[MAXM],c2[MAXM];
19 bool pd[MAXM];
20 struct ask{
21     int id,l,r,val,jilu;
22 }a[MAXM],zuo[MAXM],you[MAXM];
23 
24 inline int getint()
25 {
26        int w=0,q=0; char c=getchar();
27        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
28        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
29 }
30 
31 inline void add(LL x,LL y){
32     int cun=x;
33     while(x<=n) {
34     c1[x]+=y; c2[x]+=cun*y;
35     x+=x&(-x);
36     }
37 }
38 
39 inline LL sum(LL x){
40     LL total=0;
41     for(int i=x;i>=1;i-=(i&-i)) total+=(x+1)*c1[i]-c2[i];
42     return total;
43 }
44 
45 inline void CDQ(int askl,int askr,int l,int r){
46     if(askl>askr || l>r) return ;
47     if(l==r) { for(int i=askl;i<=askr;i++) ans[a[i].jilu]=l; return ; }//答案唯一确定了
48     int mid=(l+r+1)/2;
49     int nowl=0,nowr=0; LL now;
50     for(int i=askl;i<=askr;i++) {
51     if(a[i].id==1) {
52         if(a[i].val>=mid) add(a[i].l,1),add(a[i].r+1,-1),you[++nowr]=a[i];
53         else zuo[++nowl]=a[i];
54     }
55     else{
56         now=sum(a[i].r)-sum(a[i].l-1);//因为操作满足先后顺序，所以不会有影响
57         if(now>=a[i].val) you[++nowr]=a[i];
58         else a[i].val-=now,zuo[++nowl]=a[i];
59     }
60     }
61     for(int i=askl;i<=askr;i++) if(a[i].id==1 && a[i].val>=mid) add(a[i].l,-1),add(a[i].r+1,1); //清空
62     for(int i=1;i<=nowl;i++) a[askl+i-1]=zuo[i];
63     for(int i=1;i<=nowr;i++) a[askl+nowl+i-1]=you[i];
64     CDQ(askl,askl+nowl-1,l,mid-1);
65     CDQ(askl+nowl,askr,mid,r);
66 }
67 
68 inline void work(){
69     n=getint(); m=getint();
70     for(int i=1;i<=m;i++) { a[i].id=getint(); a[i].l=getint(); a[i].r=getint(); a[i].val=getint(); a[i].jilu=i; if(a[i].id==2) pd[i]=1; }
71     CDQ(1,m,1,n);
72     for(int i=1;i<=m;i++) if(pd[i]) printf("%d
",ans[i]);
73 }
74 
75 int main()
76 {
77   work();
78   return 0;
79 }