得之我幸cyz

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define N 100005
 8 
 9 int root[N];//root[i]表示第i課線段樹
10 int size[N*25],lchild[N*25],rchild[N*25];
11 int tot;
12 
13 void insert(int last,int cur,int L,int R,int k) //單點更新
14 {
15     size[cur]=size[last]+1;//將前一個樹的信息復制過來
16     lchild[cur]=lchild[last];
17     rchild[cur]=rchild[last];
18     if(L==R)return ;
19     int mid=L+R>>1;
20     if(k<=mid) insert(lchild[last],lchild[cur]=++tot,L,mid,k);//對于需要更改的節點都需要新增節點
21     else insert(rchild[last],rchild[cur]=++tot,mid+1,R,k);
22 }
23 int query(int last,int cur,int l,int r,int L,int R)
24 {
25     if(l>r)return 0;
26     if(L==l&&r==R){
27         return size[cur]-size[last];
28     }
29     int mid=(L+R)>>1;
30     if(l>mid)return query(rchild[last],rchild[cur],l,r,mid+1,R);
31     else if(r<=mid)return query(lchild[last],lchild[cur],l,r,L,mid);
32     else return query(rchild[last],rchild[cur],mid+1,r,mid+1,R)+query(lchild[last],lchild[cur],l,mid,L,mid);
33 }
34 int a[100005];
35 int b[100005];
36 int main(){
37     int t;
38     scanf("%d",&t);
39     int c=1;
40     while(t--){
41         int n,m;
42         scanf("%d%d",&n,&m);
43         for(int i=1;i<=n;i++){
44             scanf("%d",&a[i]);
45             b[i]=a[i];
46         }
47         sort(b+1,b+n+1);//排序
48         int nn=unique(b+1,b+n+1)-b-1;//去重
49         //上面是在離散化處理
50         tot=0;
51         for(int i=1;i<=n;i++){
52             int k=lower_bound(b+1,b+nn+1,a[i])-b;//找到a[i]在整個數列中是第幾大
53             insert(root[i-1],root[i]=++tot,1,nn,k);
54         }
55         printf("Case %d:\n",c++);
56         for(int i=1;i<=m;i++){
57             int l,r,h;
58             scanf("%d%d%d",&l,&r,&h);
59             l++;r++;
60             int k=upper_bound(b+1,b+1+nn,h)-b-1;//找到h在整個數列中是第幾大
61             printf("%d\n",query(root[l-1],root[r],1,k,1,nn));
62         }
63     }
64     return 0;
65 }

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6 const int N=5e5+6;
 7 int n,m,cnt,root[N],a[N],x,y,k;
 8 struct node
 9 {
10     int l,r,sum;
11 }T[N*40];
12 vector<int>v;
13 int getid(int x)
14 {
15     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
16 }
17 void update(int l,int r,int &x,int y,int pos)
18 {
19     T[++cnt]=T[y];
20     T[cnt].sum++;
21     x=cnt;
22     if(l==r)
23         return ;
24     int mid=(l+r)>>1;
25     if(mid>=pos)
26         update(l,mid,T[x].l,T[y].l,pos);
27     else
28         update(mid+1,r,T[x].r,T[y].r,pos);
29 }
30 int query(int l,int r,int x,int y,int k)
31 {
32     if(l==r)
33         return l;
34     int mid=(l+r)>>1;
35     int sum1=T[T[y].l].sum-T[T[x].l].sum;
36     int sum2=T[T[y].r].sum-T[T[x].r].sum;
37     if(sum1+sum1>k)
38         return query(l,mid,T[x].l,T[y].l,k);
39     if(sum2+sum2>k)
40         return query(mid+1,r,T[x].r,T[y].r,k);
41     return 0;
42 }
43 int main()
44 {
45     scanf("%d%d",&n,&m);
46     for(int i=1;i<=n;i++)
47     {
48         scanf("%d",&a[i]);
49         update(1,n,root[i],root[i-1],a[i]);
50     }
51     for(int i=1;i<=m;i++)
52     {
53         scanf("%d%d",&x,&y);
54         printf("%d\n",query(1,n,root[x-1],root[y],y-x+1));
55     }
56     return 0;
57 }

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6 const int N=1e5+6;
 7 int n,m,cnt,root[N],a[N],x,y,k;
 8 struct node
 9 {
10     int l,r,sum;
11 }T[N*40];
12 vector<int>v;
13 int getid(int x)
14 {
15     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
16 }
17 void update(int l,int r,int &x,int y,int pos)
18 {
19     T[++cnt]=T[y];
20     T[cnt].sum++;
21     x=cnt;
22     if(l==r)
23         return ;
24     int mid=(l+r)>>1;
25     if(mid>=pos)
26         update(l,mid,T[x].l,T[y].l,pos);
27     else
28         update(mid+1,r,T[x].r,T[y].r,pos);
29 }
30 int query(int l,int r,int x,int y,int k)
31 {
32     if(l==r)
33         return l;
34     int mid=(l+r)>>1;
35     int sum=T[T[y].l].sum-T[T[x].l].sum;
36     if(sum>=k)
37         return query(l,mid,T[x].l,T[y].l,k);
38     else
39         return query(mid+1,r,T[x].r,T[y].r,k-sum);
40 }
41 int main()
42 {
43     scanf("%d%d",&n,&m);
44     for(int i=1;i<=n;i++)
45     {
46         scanf("%d",&a[i]);
47         v.push_back(a[i]);
48     }
49     sort(v.begin(),v.end());
50     v.erase(unique(v.begin(),v.end()),v.end());
51     for(int i=1;i<=n;i++)
52     {
53         update(1,n,root[i],root[i-1],getid(a[i]));
54     }
55     for(int i=1;i<=m;i++)
56     {
57         scanf("%d%d%d",&x,&y,&k);
58         printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
59     }
60     return 0;

  1 #include <bits/stdc++.h>
  2 using namespace std ;
  3 bool Read ( int &x ) ///輸入掛
  4 {
  5     char c = getchar() ; x = 0 ; bool f = 0 ;
  6     while ( !isdigit(c) )
  7     {
  8         if ( c == '-' ) f = 1 ;
  9         if ( c == EOF ) return false ; c = getchar() ;
 10     }
 11     while ( isdigit(c) )
 12     { x = 10 * x + c - '0' ; c = getchar() ; }
 13     if (f) x = -x ;return true ;
 14 }
 15 void Print ( int x ) ///輸出掛
 16 {
 17     int len=0,a[50] ;
 18     if ( x == 0 ) { putchar('0') ; return ; }
 19     if ( x < 0 ) { putchar('-') ; x = -x ; }
 20     while (x) { a[++len] = x%10 ; x /= 10 ; }
 21     while (len) putchar(a[len--]+'0') ;
 22 }
 23 
 24 const int maxn=200010 ;
 25 int n,m,rt[maxn],Rank[maxn],cnt ;
 26 struct node
 27 {
 28     int l, r, v ;
 29 } tree[maxn<<5] ;
 30 struct nodd
 31 {
 32     int v, id ;
 33     friend bool operator < ( nodd a, nodd b )
 34     {
 35         return a.v == b.v ? a.id < b.id : a.v < b.v ;
 36     }
 37 } a[maxn] ;
 38 ///這個k是數據key，不是第k大，x前面有一個取地址
 39 void insert ( int K, int& x, int l, int r )
 40 {///這個是調用過程：insert(Rank[i],rt[i],1,n) ;
 41     tree[++cnt]=tree[x] ;
 42     x=cnt;///把rt[i]指向了rt[++cnt]這個真的根節點
 43     tree[x].v++;///增加數量
 44     int mid =(l+r)>>1 ;
 45     if(l==r)return ;
 46     if(K<=mid) insert(K,x[tree].l,l,mid) ;
 47     else insert(K,x[tree].r,mid+1,r) ;///節點的編號機制不是*2和*2+1
 48     ///而是根據調用次數由cnt管控，所以要存在每一個節點里
 49 }
 50 
 51 int query ( int rt1, int rt2, int l, int r, int K )
 52 {
 53     if ( l == r ) return l ;
 54     int mid = l+r >> 1 ;
 55     int num = tree[rt2].l[tree].v - tree[rt1].l[tree].v ;
 56     /**可加減性，為啥這樣做，因為幾點存的是前綴和，
 57     我們要特定區間就把前面的減去咯。
 58     你也可以這樣認為：假設查第999大，當前節點總共管3個數，
 59     你就需要把前面沒用的減去咯。*/
 60     if ( K <= num )
 61         return query ( rt1[tree].l, rt2[tree].l, l, mid, K ) ;
 62     else
 63         return query ( rt1[tree].r, rt2[tree].r, mid+1, r, K-num ) ;
 64 }
 65 
 66 int main()
 67 {
 68     int i,j,k,x,y;
 69     Read(n) ; Read(m) ;
 70     for (i=1;i<=n;i++) ///離散
 71     {
 72         Read(a[i].v) ;
 73         a[i].id=i ;
 74     }
 75     sort (a+1,a+n+1) ;
 76     for (i=1;i<=n;i++)
 77         Rank[a[i].id]=i ;
 78 
 79     for (i=1;i<=n;i++)
 80     {
 81         rt[i]=rt[i-1] ;
 82         /**
 83         一開始有棵空樹，不這樣寫，直接傳root[1]，
 84         當需要遞歸到不需要改的區間，無法找到初試樹的位置，
 85         所以暫且把初試樹的root完全復制過來
 86         這樣，因為每一棵樹的根節點存儲了它兒子的標號，
 87         所以這一步相當于第1棵樹完全等價與第0棵樹，
 88         只多開了一個root，其他的已經！！完全檢索！！到上一棵樹里
 89         然后在新的樹里把不一樣的樹枝修改成新的值，
 90         并且新開空間就行了
 91         所以之后遞歸就是if，else if，只選擇一條路，
 92         以此類推，第i棵樹繼承第i-1棵樹就行了
 93         */
 94         insert(Rank[i],rt[i],1,n);
 95     }
 96 
 97     while(m--)
 98     {
 99         Read(x);Read(y);Read(k) ;
100         Print(a[query(rt[x-1],rt[y],1,n,k)].v ) ;
101         putchar('\n') ;
102     }
103 
104     return 0 ;
105 }