4299: Codechef FRBSUM

https://www.lydsy.com/JudgeOnline/problem.php?id=4299

分析：

　　主席树。

　　https://blog.sengxian.com/solutions/bzoj-4408

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int ls[N*], rs[N*], sum[N*], Root[N], CntNode;

 void update(int l,int r,int &rt,int last,int p) {

     rt = ++CntNode;

     sum[rt] = sum[last] + p;

     if (l == r) return;

     int mid = (l + r) >> ;

     if (p <= mid) {

         rs[rt] = rs[last];

         update(l, mid, ls[rt], ls[last], p);

     }

     else {

         ls[rt] = ls[last];

         update(mid+, r, rs[rt], rs[last], p);

     }

 }

 int query(int l,int r,int Head,int Tail,int x) {

     if (l == r) {

         return sum[Tail] - sum[Head];

     }

     int mid = (l + r) >> ;

     if (x <= mid) return query(l, mid, ls[Head], ls[Tail], x);

     else return sum[ls[Tail]] - sum[ls[Head]] + query(mid+, r, rs[Head], rs[Tail], x);

 }

 int main () {

     int n = read();

     for (int i=; i<=n; ++i) {

         int x = read();

         update(, 1e9, Root[i], Root[i-], x);

     }

     int m = read();

     while (m -- ) {

         int l = read(), r = read(), ans = , tmp;

         while (true) {

             tmp = query(, 1e9, Root[l-], Root[r], ans);

             if (tmp < ans) break;

             ans = tmp + ;

         }

         printf("%d\n",ans);

     }

     return ;

 }