解题：ZJOI 2013 K大数查询

树套树，权值线段树套序列线段树，每次在在权值线段树上的每棵子树上做区间加，查询的时候左右子树二分

本来想两个都动态开点的，这样能体现树套树在线的优越性。但是常数太大惹，所以外层直接固定建树了QAQ

就是不写整体二分╭(╯^╰)╮

Warning：Extremely ugly code detected

  1 // luogu-judger-enable-o2
  2 //I CAN PASS THE TEST
  3 #include<cstdio>
  4 #include<cctype>
  5 #include<cstring>
  6 #include<algorithm>
  7 using namespace std;
  8 const int N=14000000;
  9 int n,m,f,op,tot; 
 10 long long val[N];
 11 int root[N],lson[N],rson[N],laz[N];
 12 void read1(int &x)
 13 {
 14     x=0; char ch=getchar();
 15     while(!isdigit(ch))
 16         ch=getchar();
 17     while(isdigit(ch))
 18         x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
 19 }
 20 void read2(int &x)
 21 {
 22     x=f=0; char ch=getchar();
 23     while(!isdigit(ch))
 24         f|=ch=='-',ch=getchar();
 25     while(isdigit(ch))
 26         x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
 27     x=f?-x:x;
 28 }
 29 void read3(long long &x)
 30 {
 31     x=0; char ch=getchar();
 32     while(!isdigit(ch))
 33         ch=getchar();
 34     while(isdigit(ch))
 35         x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
 36 }
 37 void write(int x)
 38 {
 39     if(x>9) write(x/10);
 40     putchar(x%10|48);
 41 }
 42 void Insert(int &nde,int ll,int rr,int l,int r)
 43 {
 44     if(ll>r||rr<l) return ;
 45     if(!nde) nde=++tot;
 46     val[nde]+=min(r,rr)-max(l,ll)+1;
 47     if(ll>=l&&rr<=r)
 48            ++laz[nde];
 49     else
 50     {
 51         int mid=(ll+rr)>>1;
 52         Insert(lson[nde],ll,mid,l,r);
 53         Insert(rson[nde],mid+1,rr,l,r);
 54     }
 55 } 
 56 void Add(int l,int r,int v)
 57 {
 58     int nde=1,ll=1,rr=2*n;
 59     while(true)
 60     {
 61         Insert(root[nde],1,n,l,r);
 62         if(ll^rr)
 63         {
 64             int mid=(ll+rr)>>1;
 65             (v<=mid)?(nde<<=1,rr=mid):(nde<<=1,nde|=1,ll=mid+1); 
 66         }
 67         else return ;
 68     }
 69 }
 70 long long Query(int nde,int ll,int rr,int l,int r,int lz)
 71 {     
 72     if(ll>r||rr<l) 
 73         return 0;
 74     else if(ll>=l&&rr<=r) 
 75         return val[nde]+1ll*lz*(rr-ll+1);
 76     else
 77     {
 78         int mid=(ll+rr)>>1;
 79         return Query(lson[nde],ll,mid,l,r,lz+laz[nde])+Query(rson[nde],mid+1,rr,l,r,lz+laz[nde]);
 80     }
 81 }
 82 int main()
 83 {
 84     register int i;
 85     read1(n),read1(m);
 86     for(i=1;i<=m;i++)
 87     {
 88         read1(op);
 89         if(op==1)
 90         {
 91             int t1,t2,t3;
 92             read1(t1),read1(t2),read2(t3);
 93             int nde=1,ll=1,rr=2*n; t3=n-t3+1;
 94             while(true)
 95             {
 96                 Insert(root[nde],1,n,t1,t2);
 97                 if(!(ll^rr)) break;
 98                 int mid=(ll+rr)>>1;
 99                 (t3<=mid)?(nde<<=1,rr=mid):(nde<<=1,nde|=1,ll=mid+1); 
100             }
101         }
102         else 
103         {
104             int t1,t2; long long t4;
105             read1(t1),read1(t2),read3(t4);
106             int nde=1,ll=1,rr=2*n;
107             while(true)
108             {
109                 if(ll==rr) {write(n-ll+1),puts(""); break;}
110                 int mid=(ll+rr)/2; 
111                 long long qry=Query(root[nde<<1],1,n,t1,t2,0);
112                 (t4<=qry)?(nde<<=1,rr=mid):(nde<<=1,nde|=1,ll=mid+1,t4-=qry);
113             }
114         }
115     }
116     return 0;
117 }

View Code