주석 트리 트리 트리 그룹 동적 구간 k소
30500 단어 트리 배열
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 #include <cstring>
5 #include <cmath>
6 #define REP(i, s, n) for(int i = s; i <= n; i ++)
7 #define RAP(i, n, s) for(int i = n; i >= s; i --)
8 #define LOW for(; x; x -= x & (-x))
9 using namespace std;
10 const int maxn = 100000 + 10;
11 const int Maxn = 100000;
12 const int maxnode = 200 * maxn;
13 int s[maxnode], ls[maxnode], rs[maxnode], A[maxn], root[maxn], Ln, Rn, L[maxn], R[maxn], c[maxn];
14 int n, Q, ms = 0;
15 void update(int x, int& y, int L, int R, int pos, int v){
16 s[y = ++ ms] = s[x] + v;
17 if(L == R) return ;
18 int M = L + R >> 1;
19 ls[y] = ls[x]; rs[y] = rs[x];
20 if(pos <= M) update(ls[x], ls[y], L, M, pos, v);
21 else update(rs[x], rs[y], M + 1, R, pos, v);
22 return ;
23 }
24 void update(int x, int v){
25 for(int i = x; i <= Maxn; i += i & (-i)) update(c[i], c[i], 1, Maxn, A[x], -1); A[x] = v;
26 for(int i = x; i <= Maxn; i += i & (-i)) update(c[i], c[i], 1, Maxn, A[x], 1); return ;
27 }
28 void init(int x, int tp){
29 if(!tp) { L[++ Ln] = root[x]; LOW if(c[x]) L[++ Ln] = c[x]; }
30 else { R[++ Rn] = root[x]; LOW if(c[x]) R[++ Rn] = c[x]; }
31 return ;
32 }
33 int query(int ql, int qr, int k){
34 Ln = Rn = 0; init(qr, 1); init(ql - 1, 0);//0
35 int ll = 1, rr = Maxn;
36 while(ll < rr){
37 int Lsum = 0, Rsum = 0, M = ll + rr >> 1;
38 REP(i, 1, Ln) Lsum += s[ls[L[i]]];
39 REP(i, 1, Rn) Rsum += s[ls[R[i]]];
40 int kth = Rsum - Lsum;
41 if(kth >= k){//
42 REP(i, 1, Ln) L[i] = ls[L[i]];
43 REP(i, 1, Rn) R[i] = ls[R[i]];
44 rr = M;
45 }
46 else{//
47 REP(i, 1, Ln) L[i] = rs[L[i]];
48 REP(i, 1, Rn) R[i] = rs[R[i]];
49 ll = M + 1; k -= kth; // ! Σ( ° △ °|||)︴
50 }
51 }
52 return ll;
53 }
54 inline void read(int &x){
55 x = 0; int sig = 1; char ch = getchar();
56 while(!isdigit(ch)) { if(ch == '-') sig = -1; ch = getchar(); }
57 while(isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
58 x *= sig; return ;
59 }
60 inline void write(int x){
61 if(x == 0) { putchar('0'); return ; }
62 if(x < 0) putchar('-'), x = -x;
63 int len = 0, buf[20];
64 while(x) buf[len ++] = x % 10, x /= 10;
65 RAP(i, len - 1, 0) putchar(buf[i] + '0'); return ;
66 }
67 void init(){
68 read(n); read(Q);
69 REP(i, 1, n) read(A[i]);
70 REP(i, 1, n) update(root[i - 1], root[i], 1, Maxn, A[i], 1);
71 return ;
72 }
73 void work(){
74 int tp, ql, qr, k, x, v;
75 while(Q --){
76 read(tp);
77 if(tp) read(ql), read(qr), read(k), write(query(ql, qr, k) - 1), putchar('
');//
78 else read(x), read(v), update(x, v);
79 }
80 return ;
81 }
82 void print(){
83
84 return ;
85 }
86 int main(){
87 init();
88 work();
89 print();
90 return 0;
91 }
비교:
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #define t node[d]
6 #define cnt countn[d]
7 #define repnode(d) for(int i=1;i<=countn[d];i++)
8 using namespace std;
9 const int maxn=100000+10,maxnode=20000000+10,Max=100000;
10 int ls[maxnode],rs[maxnode],s[maxnode],root[maxn],A[maxn],c[maxn],n,m,ms=0,countn[2],node[2][maxn],sum[2];
11 void update(int x,int& y,int L,int R,int pos,int d){
12 s[y=++ms]=s[x]+d;
13 if(L==R) return;
14 ls[y]=ls[x];rs[y]=rs[x];
15 int M=L+R>>1;
16 if(pos<=M) update(ls[x],ls[y],L,M,pos,d);
17 else update(rs[x],rs[y],M+1,R,pos,d);
18 return;
19 }
20 void update(int x,int v){
21 for(int i=x;i<=Max;i+=i&-i) update(c[i],c[i],1,Max,A[x],-1);A[x]=v;
22 for(int i=x;i<=Max;i+=i&-i) update(c[i],c[i],1,Max,A[x],1);return;
23 }
24 void init(int x,int d){
25 t[++cnt]=root[x];
26 for(;x;x-=x&-x) if(c[x]) t[++cnt]=c[x];
27 return;
28 }
29 int query(int ql,int qr,int k){
30 countn[0]=countn[1]=0;
31 init(qr,1);init(ql-1,0);
32 int L=1,R=Max,d;
33 while(L<R){
34 sum[0]=sum[1]=0;
35 int M=L+R>>1;
36 repnode(d=0) sum[d]+=s[ls[t[i]]];
37 repnode(d=1) sum[d]+=s[ls[t[i]]];
38 int kth=sum[1]-sum[0];
39 if(k<=kth){
40 repnode(d=0) t[i]=ls[t[i]];
41 repnode(d=1) t[i]=ls[t[i]];
42 R=M;
43 }
44 else{
45 repnode(d=0) t[i]=rs[t[i]];
46 repnode(d=1) t[i]=rs[t[i]];
47 L=M+1;k-=kth;
48 }
49 } return L;
50 }
51 inline int read(){
52 int x=0,sig=1;char ch=getchar();
53 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
54 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
55 return x*=sig;
56 }
57 inline void write(int x){
58 if(x==0){putchar('0');return;} if(x<0) putchar('-'),x=-x;
59 int len=0,buf[15]; while(x) buf[len++]=x%10,x/=10;
60 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
61 }
62 void init(){
63 n=read();m=read();
64 for(int i=1;i<=n;i++) A[i]=read();
65 for(int i=1;i<=n;i++) update(root[i-1],root[i],1,Max,A[i],1);
66 return;
67 }
68 void work(){
69 int tp,i,j,k,x,v;
70 while(m--){
71 tp=read();
72 if(tp){
73 i=read();j=read();k=read();
74 write(query(i,j,k)-1);putchar('
');
75 }
76 else{
77 x=read();v=read();
78 update(x,v);
79 }
80 }
81 return;
82 }
83 void print(){
84 return;
85 }
86 int main(){
87 init();work();print();return 0;
88 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu2227---Find the nondecreasing subsequences (dp+ 트리 배열)Problem Description How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, …., sn} ? For exam...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.