P2839 [国家集训队]middle

题面

　　• 提一下静态区间第k小的nlog²n的做法：

　　　　1. 建关于排名的主席树（按排名顺序建树）。

　　　　2. 二分答案。

　　• 这样做静态区间第k小的虽然有些ZZ，但它的意义在于将线段树

　　维护的对象改变了。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int n,m,cnt;
  4 int a[5],midd;
  5 int val[20050];
  6 int pos[20050];
  7 int root[20050];
  8 int son[500050][2];
  9 struct node
 10 {
 11     int sum,l,r;
 12     void clear()
 13     {
 14         sum=0;
 15         l=r=0;
 16     }
 17 }w[500050],ans;
 18 node merge(node a,node b)
 19 {
 20     node tmp;
 21     tmp.sum=a.sum+b.sum;
 22     tmp.l=max(a.l,a.sum+b.l);
 23     tmp.r=max(b.r,b.sum+a.r);
 24     return tmp;
 25 }
 26 bool cmp(int x,int y)
 27 {
 28     return val[x]<val[y];
 29 }
 30 void build(int &u,int l,int r)
 31 {
 32     u=++cnt;
 33     if(l==r)
 34     {
 35         w[u].sum=r-l+1;
 36         w[u].l=w[u].r=r-l+1;
 37         return ;
 38     }
 39     int mid=(l+r)>>1;
 40     build(son[u][0],l,mid);
 41     build(son[u][1],mid+1,r);
 42     w[u]=merge(w[son[u][0]],w[son[u][1]]);
 43 }
 44 void calc(int &u,int v,int l,int r,int pos)
 45 {
 46     u=++cnt;w[u]=w[v];
 47     son[u][0]=son[v][0];
 48     son[u][1]=son[v][1];
 49     if(l==r)
 50     {
 51         w[u].sum=-1;
 52         w[u].l=w[u].r=-1;
 53         return ;
 54     }
 55     int mid=(l+r)>>1;
 56     if(pos<=mid)    calc(son[u][0],son[v][0],l,mid,pos);
 57     else            calc(son[u][1],son[v][1],mid+1,r,pos);
 58     w[u]=merge(w[son[u][0]],w[son[u][1]]);
 59 }
 60 void ask(int u,int l,int r,int L,int R)
 61 {
 62     if(L<=l&&r<=R)
 63     {
 64         ans=merge(ans,w[u]);
 65         return ;
 66     }
 67     int mid=(l+r)>>1;
 68     if(L<=mid)    ask(son[u][0],l,mid,L,R);
 69     if(R>mid)    ask(son[u][1],mid+1,r,L,R);
 70 }
 71 bool check(int u)
 72 {
 73     int sum=0;
 74     if(a[2]+1<=a[3])    
 75     {
 76         ans.clear();
 77         ask(root[u],1,n,a[2]+1,a[3]);
 78         sum+=ans.sum;
 79     }
 80     if(a[1]<=a[2])
 81     {
 82         ans.clear();
 83         ask(root[u],1,n,a[1],a[2]);
 84         sum+=ans.r;
 85     }
 86     if(a[3]+1<=a[4])
 87     {
 88         ans.clear();
 89         ask(root[u],1,n,a[3]+1,a[4]);
 90         sum+=ans.l;
 91     }
 92     return sum>=0;
 93 }
 94 int main()
 95 {
 96     scanf("%d",&n);
 97     for(int i=1;i<=n;++i)
 98     {
 99         scanf("%d",&val[i]);
100         pos[i]=i;
101     }
102     sort(pos+1,pos+n+1,cmp);
103     build(root[0],1,n);
104     for(int i=1;i<=n;++i)
105         calc(root[i],root[i-1],1,n,pos[i]);
106     scanf("%d",&m);
107     while(m--)
108     {
109         for(int i=1;i<=4;++i)
110         {
111             scanf("%d",&a[i]);
112             a[i]=(a[i]+midd)%n+1;
113         }
114         sort(a+1,a+5);
115         int l=1,r=n;
116         while(l<r)
117         {
118             int mid=(l+r+1)>>1;
119             if(check(mid))    l=mid;
120             else    r=mid-1;
121         }
122         midd=val[pos[l+1]];
123         printf("%d
",midd);
124     }
125     return 0;
126 }

View Code