用于记录所用的：
参考博客:
「分块」数列分块入门1 – 9 by hzwer
1 #include<cmath> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 const int N = 5e4+100; 6 int L[N],R[N]; //第i块的左右边界下标 7 int pos[N]; //下标标记,通过下标找块号 8 int add[N]; //块内增量 9 int a[N],n; 10 inline int read(){ 11 char c = getchar(); 12 int x = 0 ,f=1 ; 13 while ( !('0'<= c && c<='9') ){ 14 c = getchar(); 15 if ( c=='-') f=-1 ; 16 } 17 while ('0'<= c && c<='9'){ 18 x = x*10 + c-'0'; 19 c = getchar(); 20 } 21 return x * f ; 22 } 23 void change(int x,int y,int c){ 24 int p = pos[x] , q = pos[y]; 25 //同一个块时 26 if( p==q ) for(int i=x;i<=y;i++){ a[i] += c ; } 27 //不同块时 28 else{ 29 //中间的块直接加增量到add上 30 for(int i=p+1;i<=q-1;i++) add[i] += c; 31 //块内直接暴力跑 32 for(int i=x;i<=R[p];i++) 33 a[i] += c ; 34 for(int i=L[q];i<=y;i++) 35 a[i] += c ; 36 } 37 } 38 int main() 39 { 40 n = read(); 41 for(int i=1;i<=n;i++) a[i] = read(); 42 int block = sqrt(n) ; 43 for(int i=1;i<=block;i++){ 44 L[i] = (i-1)*block + 1 ; 45 R[i] = i * block ; 46 } 47 if( R[block] < n ){ 48 block ++ ; 49 L[block] = R[block-1]+1 ; 50 R[block] = n ; 51 } 52 for(int i=1;i<=block;i++){ 53 for(int j=L[i];j<=R[i];j++){ 54 pos[j] = i ; 55 } 56 } 57 int opt,x,y,c; 58 for(int i=1;i<=n;i++){ 59 opt = read(); 60 x = read(); 61 y = read(); 62 c = read(); 63 if( opt == 0 ){ 64 change( x,y,c ); 65 }else{ 66 int No = pos[y]; 67 printf("%d ",a[y] + add[No]); 68 } 69 } 70 return 0; 71 }
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 #include<vector> 5 #include<algorithm> 6 using namespace std; 7 const int N = 5e4+100; 8 const int M = 505; 9 int a[N],pos[N],add[N]; 10 int n,block; 11 vector <int> vec[M]; 12 template <class T> 13 void read(T& x){ 14 x = 0; 15 int f = 1 ; 16 char c = getchar(); 17 while( !isdigit(c) ){ 18 if ( c=='-' ) f = -1 ; 19 c = getchar(); 20 } 21 while( isdigit(c) ){ 22 x = x * 10 + c-'0'; 23 c = getchar(); 24 } 25 x = x*f; 26 } 27 inline void reset(int No){ 28 vec[No].clear(); 29 for(int i=(No-1)*block+1;i<=min(No*block,n);i++) 30 vec[No].push_back(a[i]); 31 sort( vec[No].begin(),vec[No].end() ); 32 } 33 inline void modify(int x,int y,int c){ 34 int p = pos[x] , q = pos[y] ; 35 //同一块内 36 if( p == q ){ 37 for(int i=x;i<=y;i++) 38 a[i] += c ; 39 reset(p); 40 }else{ 41 for(int i=x;i<=pos[x]*block;i++) 42 a[i] += c; 43 reset(pos[x]); 44 45 for(int i=(pos[y]-1)*block+1;i<=y;i++) 46 a[i] += c; 47 reset(pos[y]); 48 49 for(int i=pos[x]+1;i<=pos[y]-1;i++){ 50 add[i] += c ; 51 } 52 } 53 } 54 inline int query(int x,int y,int c){ 55 int p = pos[x] , q = pos[y] ; 56 int ans = 0 ; 57 //同一块内 58 if( p == q ){ 59 for(int i=x;i<=y;i++) 60 if( a[i] + add[p] < c ) ans ++ ; 61 }else{ 62 for(int i=x;i<=pos[x]*block;i++){ 63 if( a[i] + add[p] < c ) ans ++ ; 64 } 65 for(int i=(pos[y]-1)*block+1;i<=y;i++){ 66 if( a[i] + add[q] < c ) ans ++ ; 67 } 68 for(int i=pos[x]+1;i<=pos[y]-1;i++){ 69 ans += lower_bound(vec[i].begin(),vec[i].end(),c-add[i]) - vec[i].begin(); 70 } 71 } 72 return ans ; 73 } 74 int main() 75 { 76 read(n); 77 //printf("%d ",n); 78 block = (int) sqrt(n); 79 for(int i=1;i<=n;i++) read(a[i]); 80 for(int i=1;i<=n;i++){ 81 pos[i] = (i-1) / block + 1 ; 82 vec[pos[i]].push_back(a[i]); 83 } 84 for(int i=1;i<=pos[n];i++) 85 sort(vec[i].begin(),vec[i].end()); 86 int opt , x , y , c ; 87 for(int i=1;i<=n;i++){ 88 read(opt),read(x),read(y),read(c); 89 if( opt == 0 ){ 90 modify(x,y,c); 91 }else{ 92 printf("%d ",query(x,y,c*c)); 93 } 94 } 95 return 0 ; 96 }
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 #include<vector> 5 #include<algorithm> 6 using namespace std; 7 const int N = 1e5+100; 8 const int M = 1005; 9 int a[N],pos[N],add[N]; 10 int n,block; 11 vector <int> vec[M]; 12 template <class T> 13 void read(T& x){ 14 x = 0; 15 int f = 1 ; 16 char c = getchar(); 17 while( !isdigit(c) ){ 18 if ( c=='-' ) f = -1 ; 19 c = getchar(); 20 } 21 while( isdigit(c) ){ 22 x = x * 10 + c-'0'; 23 c = getchar(); 24 } 25 x = x*f; 26 } 27 inline void reset(int No){ 28 vec[No].clear(); 29 for(int i=(No-1)*block+1;i<=min(No*block,n);i++) 30 vec[No].push_back(a[i]); 31 sort( vec[No].begin(),vec[No].end() ); 32 } 33 inline void modify(int x,int y,int c){ 34 int p = pos[x] , q = pos[y] ; 35 //同一块内 36 if( p == q ){ 37 for(int i=x;i<=y;i++) 38 a[i] += c ; 39 reset(p); 40 }else{ 41 for(int i=x;i<=pos[x]*block;i++) 42 a[i] += c; 43 reset(pos[x]); 44 45 for(int i=(pos[y]-1)*block+1;i<=y;i++) 46 a[i] += c; 47 reset(pos[y]); 48 49 for(int i=pos[x]+1;i<=pos[y]-1;i++){ 50 add[i] += c ; 51 } 52 } 53 } 54 inline int query(int x,int y,int c){ 55 int p = pos[x] , q = pos[y] ; 56 int ans = -1 , tmp ; 57 //同一块内 58 if( p == q ){ 59 for(int i=x;i<=y;i++) 60 if( a[i] + add[p] < c ) ans = max(ans,a[i]+add[p]); 61 }else{ 62 for(int i=x;i<=pos[x]*block;i++){ 63 if( a[i] + add[p] < c ) ans = max(ans,a[i]+add[p]) ; 64 } 65 for(int i=(pos[y]-1)*block+1;i<=y;i++){ 66 if( a[i] + add[q] < c ) ans = max(ans,a[i]+add[q]); 67 } 68 for(int i=pos[x]+1;i<=pos[y]-1;i++){ 69 tmp = lower_bound(vec[i].begin(),vec[i].end(),c-add[i]) - vec[i].begin(); 70 if( tmp != 0 ){ 71 ans = max(ans,vec[i][tmp-1]+add[i]); 72 } 73 } 74 } 75 return ans ; 76 } 77 int main() 78 { 79 read(n); 80 //printf("%d ",n); 81 block = (int) sqrt(n); 82 for(int i=1;i<=n;i++) read(a[i]); 83 for(int i=1;i<=n;i++){ 84 pos[i] = (i-1) / block + 1 ; 85 vec[pos[i]].push_back(a[i]); 86 } 87 for(int i=1;i<=pos[n];i++) 88 sort(vec[i].begin(),vec[i].end()); 89 int opt , x , y , c ; 90 for(int i=1;i<=n;i++){ 91 read(opt),read(x),read(y),read(c); 92 if( opt == 0 ){ 93 modify(x,y,c); 94 }else{ 95 printf("%d ",query(x,y,c)); 96 } 97 } 98 return 0 ; 99 }
#include<iostream> #include<cctype> #include<cstdio> #include<cmath> #define ll long long using namespace std; const int N = 5e4+50; ll add[N],sum[N],a[N]; int pos[N],L[N],R[N]; int n,block; int opt,l,r,c; inline int read (){ int x = 0 , f = 1 ; char c = getchar() ; while( !isdigit(c) ){ if( c == '-' ) f = -1 ; c = getchar(); } while( isdigit(c) ){ x = ((x << 1) + (x << 3)) + c - '0'; c = getchar(); } return x * f ; } inline void Modify(int l,int r,int c){ int p = pos[l] , q = pos[r]; if( p==q ){ for(int i = l ; i <= r ;i++ ) a[i] += c ; sum[p] += (r-l+1)*c; }else{ for(int i=l;i<=R[p];i++) a[i] += c; sum[p] += (R[p]-l+1) * c ; for(int i=L[q];i<=r;i++) a[i] += c; sum[q] += (r-L[q]+1) * c ; for(int i=p+1;i<=q-1;i++) add[i] += c ; } } inline ll Query(int l,int r,int mod){ int p = pos[l] , q = pos[r]; ll ans = 0 ; if( p==q ){ for(int i=l;i<=r;i++) ans = ( ans + a[i] ) % mod ; ans = ( ans + (r-l+1) * add[q] ) % mod ; }else{ for(int i=l;i<=R[p];i++) ans = ( ans + a[i] ) % mod ; ans = ( ans + (R[p]-l+1) * add[p] ) % mod ; for(int i=L[q] ; i<=r ;i++ ) ans = ( ans + a[i] ) %mod ; ans = ( ans + (r-L[q]+1) * add[q] ) % mod ; for(int i=p+1;i<=q-1;i++) ans = ( ans + sum[i] + (R[i]-L[i]+1)*add[i] ) %mod ; } return ans % mod ; } int main() { n = read() ; block = sqrt(n) ; for(int i=1;i<=n;i++) a[i] = read(); for(int i=1;i<=block;i++){ L[i] = (i-1) * block + 1 ; R[i] = i * block ; } if( R[block] < n ){ block ++ ; L[block] = R[block-1] + 1 ; R[block] = n ; } for(int i=1;i<=block;i++){ for(int j=L[i];j<=R[i];j++){ pos[j] = i ; sum[i] += a[j]; } } for(int i=1;i<=n;i++){ opt = read() , l = read() ,r = read() ,c = read(); if ( !opt ) Modify(l,r,c); else cout << Query(l,r,c+1) << endl ; } return 0 ; }
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 5e4+100; 5 int L[N],R[N],pos[N],vis[N]; 6 int sum[N],a[N]; 7 int n,block,opt,l,r,c; 8 9 template <class T> 10 void read ( T & x ){ 11 x = 0 ; 12 int f = 1 ; 13 char c = getchar( ); 14 while ( !isdigit(c) ){ 15 if ( c=='-' ) f = -1; 16 c = getchar(); 17 } 18 while ( isdigit(c) ){ 19 x = ( (x<<3) + (x<<1) ) + c-'0' ; 20 c = getchar(); 21 } 22 x = x * f ; 23 } 24 25 void check_sqrt(int No){ 26 if( vis[No] ) return ; 27 vis[No] = 1 ; 28 sum[No] = 0 ; 29 for(int i=L[No];i<=R[No];i++){ 30 a[i] = (int)sqrt(a[i]); 31 sum[No] += a[i]; 32 if( a[i] > 1 ) 33 vis[No] = 0 ; 34 } 35 } 36 inline void Modify(int l,int r){ 37 int p = pos[l] , q = pos[r] ; 38 if( p == q ){ 39 for(int i=l;i<=r;i++){ 40 sum[p] -= a[i] ; 41 a[i] = (int)sqrt(a[i]); 42 sum[p] += a[i]; 43 } 44 }else{ 45 for(int i=l;i<=R[p];i++){ 46 sum[p] -= a[i] ; 47 a[i] = (int)sqrt(a[i]); 48 sum[p] += a[i]; 49 } 50 for(int i=L[q];i<=r;i++){ 51 sum[q] -= a[i] ; 52 a[i] = (int)sqrt(a[i]); 53 sum[q] += a[i]; 54 } 55 for(int i=p+1;i<=q-1;i++) check_sqrt(i); 56 } 57 } 58 inline ll Query(int l,int r ){ 59 int p = pos[l] , q = pos[r] ; 60 ll ans = 0 ; 61 if ( p==q ) { 62 for(int i=l;i<=r;i++) ans += a[i]; 63 }else{ 64 for(int i=l;i<=R[p];i++) ans += a[i] ; 65 for(int i=L[q];i<=r;i++) ans += a[i] ; 66 for(int i=p+1;i<=q-1;i++){ 67 ans += sum[i] ; 68 } 69 } 70 return ans ; 71 } 72 int main() 73 { 74 read(n);block = sqrt(n); 75 for(int i=1;i<=n;i++) read(a[i]) ; 76 for(int i=1;i<=block;i++){ 77 L[i] = (i-1)*block + 1 ; 78 R[i] = i * block ; 79 } 80 if ( R[block] < n ) { 81 block ++ ; 82 L[block] = R[block-1] + 1 ; 83 R[block] = n ; 84 } 85 for(int i=1;i<=block;i++){ 86 for(int j=L[i];j<=R[i];j++){ 87 pos[j] = i ; 88 sum[i] += a[j]; 89 } 90 } 91 for(int i=1;i<=n;i++){ 92 read(opt),read(l),read(r),read(c); 93 if( !opt ) Modify(l,r); 94 else printf("%lld ",Query(l,r)); 95 } 96 }
1 #include<bits/stdc++.h> 2 #define Mp make_pair 3 #define F first 4 #define S second 5 using namespace std; 6 const int N = 1e5+100; 7 const int M = 10005; 8 typedef pair<int,int> PII; 9 int n,a[N],k,m; 10 int s[N<<1]; 11 int opt,L,R,c; 12 vector<int>Vec[M]; 13 template <class T> 14 void read( T &x ){ 15 x = 0 ; 16 int f = 1 ; 17 char c = getchar() ; 18 while( !isdigit(c) ){ 19 if( c=='-' ) f = -1 ; 20 c = getchar() ; 21 } 22 while( isdigit(c) ){ 23 x = x*10 + c-'0'; 24 c = getchar(); 25 } 26 x = x * f; 27 } 28 PII Query(int x){ 29 int No = 1 ; 30 while ( x > (int) Vec[No].size() ){ 31 x -= (int) Vec[No].size(); 32 No++; 33 } 34 return Mp(No,x-1); 35 } 36 void rebuild(){ 37 int cnt = 0 ; 38 for(int i=1;i<=m;i++){ 39 int sz = Vec[i].size(); 40 for(int j=0;j<sz;j++) 41 s[ ++cnt ] = Vec[i][j] ; 42 Vec[i].clear(); 43 } 44 k = sqrt(cnt) ; 45 m = (cnt-1)/k + 1 ; 46 for(int i=1;i<=cnt;i++){ 47 Vec[(i-1)/k+1].push_back( s[i] ); 48 } 49 } 50 void Modify(int L,int R){ 51 PII x = Query(L); 52 int f = x.F; 53 int s = x.S; 54 Vec[f].insert(Vec[f].begin()+s,R); 55 if( (int) Vec[f].size() > 20 * k ) 56 rebuild(); 57 } 58 int main() 59 { 60 read(n); k = sqrt(n) ; 61 for(int i=1;i<=n;i++){ 62 read(a[i]); 63 Vec[(i-1)/k+1].push_back(a[i]); 64 } 65 m = (n-1)/k+1; 66 67 for(int i=1;i<=n;i++){ 68 read(opt),read(L),read(R),read(c); 69 if( !opt ){ 70 Modify(L,R); 71 }else{ 72 PII tmp = Query(R); 73 printf("%d ",Vec[tmp.F][tmp.S]); 74 } 75 } 76 return 0 ; 77 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 const int M = 1e3+100; 5 const int mod = 10007; 6 typedef long long ll; 7 int L[M],R[M],pos[N]; 8 ll a[N],mul[M],add[M]; 9 int n,block; 10 int opt,l,r,c; 11 12 template <class T> 13 inline void read( T& x ){ 14 x = 0 ; 15 int f = 1 ; 16 char c = getchar(); 17 while( !isdigit(c) ){ 18 if ( c=='-' ) f = -1 ; 19 c = getchar(); 20 } 21 while( isdigit(c) ){ 22 x = ( (x<<1) + (x<<3) ) + c-'0'; 23 c = getchar(); 24 } 25 x = x*f ; 26 } 27 28 inline void reset(int No){ 29 for(int i=(No-1)*block+1;i<=min(No*block,n);i++){ 30 a[i] = ( a[i] * mul[No] + add[No]) % mod ; 31 } 32 add[No] = 0 ; 33 mul[No] = 1 ; 34 } 35 inline void Modify(int opt,int l,int r,ll c ){ 36 int p = pos[l], q = pos[r]; 37 if( p == q ){ 38 reset( p ); 39 for(int i=l;i<=r;i++){ 40 if(!opt) a[i] = (a[i] + c ) % mod; 41 else a[i] = (a[i] * c ) % mod ; 42 } 43 }else{ 44 reset( p ); 45 for(int i=l;i<=block*p;i++){ 46 if(!opt) a[i] = (a[i] + c ) % mod; 47 else a[i] = (a[i] * c ) % mod ; 48 } 49 reset( q ); 50 for(int i=(q-1)*block+1;i<=r;i++){ 51 if(!opt) a[i] = (a[i] + c ) % mod; 52 else a[i] = (a[i] * c ) % mod ; 53 } 54 for(int i=p+1;i<=q-1;i++){ 55 if(!opt) add[i] = ( add[i] + c ) % mod ; 56 else { 57 add[i] = (add[i]*c) % mod ; 58 mul[i] = (mul[i]*c) % mod ; 59 } 60 } 61 } 62 } 63 int main() 64 { 65 read(n); block = sqrt(n); 66 for(int i=1;i<=n;i++) { 67 read(a[i]); 68 pos[i] = (i-1)/block + 1 ; 69 } 70 for(int i=1;i<=pos[n];i++) mul[i] = 1 ; 71 /* 72 for(int i=1;i<=block;i++){ 73 L[i] = (i-1)*block + 1 ; 74 R[i] = i*block; 75 } 76 if( R[block] < n ){ 77 block ++; 78 L[block] = R[block] + 1 ; 79 R[block] = n ; 80 } 81 for(int i=1;i<=block;i++){ 82 for(int j=L[i];j<=R[i];j++) 83 pos[j] = i ; 84 mul[i] = 1 ; 85 } 86 */ 87 for(int i=1;i<=n;i++){ 88 read(opt),read(l),read(r),read(c); 89 if( opt == 2 ) 90 printf("%lld ",1ll * (a[r] * mul[pos[r]] + add[pos[r]]) %mod ) ; 91 else 92 Modify( opt,l,r,c); 93 } 94 return 0; 95 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 1e5+10; 5 int vis[N],a[N],pos[N]; 6 int n,block; 7 int l,r,c; 8 template <class T> 9 void read( T &x ){ 10 x = 0 ; 11 int f = 1 ; 12 char c = getchar(); 13 while( !isdigit(c) ){ 14 if ( c=='-' ) f = -1 ; 15 c = getchar() ; 16 } 17 while( isdigit(c) ){ 18 x = ( (x<<1) + (x<<3) ) + c - '0' ; 19 c = getchar() ; 20 } 21 x = x * f; 22 } 23 24 void reset(int No){ 25 if( vis[No] == -1 ){ 26 //puts("****"); 27 return ; 28 } 29 for(int i=(No-1)*block+1;i<=min(No*block,n);i++){ 30 a[i] = vis[No] ; 31 } 32 vis[No] = -1 ; 33 } 34 35 int solve(int L,int R,int c ){ 36 int p = pos[L] , q = pos[R] ; 37 int ans = 0 ; 38 if( p == q ){ 39 reset(p) ; 40 for(int i=L;i<=R;i++){ 41 if( a[i] == c ) ans ++ ; 42 else a[i] = c ; 43 } 44 45 }else{ 46 reset(p) ; 47 for(int i=L;i<=p*block;i++){ 48 if( a[i] == c ) { 49 ans ++ ; 50 //printf("# "); 51 } 52 else a[i] = c ; 53 } 54 55 reset(q) ; 56 for(int i=(q-1)*block+1;i<=R;i++){ 57 if( a[i] == c ) { 58 ans ++ ; 59 //printf("(%d ,%d) $ ",i,a[i]); 60 } 61 else a[i] = c ; 62 } 63 64 for(int i=p+1;i<=q-1;i++){ 65 if( vis[i] != -1 ){ 66 if( vis[i] == c ) 67 ans += block ; 68 69 }else{ 70 for(int j=(i-1)*block+1;j<=i*block;j++){ 71 if( a[j] != c ) a[j] = c ; 72 else ans ++ ; 73 } 74 } 75 vis[i] = c ; 76 } 77 } 78 return ans ; 79 } 80 int main(){ 81 memset(vis,-1,sizeof vis ); 82 read(n); block = (int)sqrt(n); 83 //printf("@@@%d ",block); 84 for(int i=1;i<=n;i++){ 85 read(a[i]); 86 87 pos[i] = (i-1)/block + 1 ; 88 //printf("#%d#",pos[i]); 89 } 90 91 for(int i=1;i<=n;i++){ 92 read(l),read(r),read(c); 93 printf("%d ",solve(l,r,c)); 94 } 95 return 0 ; 96 }
1 #include<map> 2 #include<cmath> 3 #include<cstdio> 4 #include<vector> 5 #include<cstring> 6 #include<algorithm> 7 #define all(d) (d).begin(),(d).end() 8 #define U_b upper_bound 9 #define L_b lower_bound 10 using namespace std; 11 const int N = 1e5+100; 12 const int M = 1005; 13 int f[M][M]; 14 int a[N],pos[N]; 15 int val[N],cnt[N]; 16 int n,l,r,t,id; 17 map<int,int>Mp; 18 vector<int> v[N]; 19 template <class T> 20 void read(T &x ){ 21 x = 0 ; 22 int f = 1 ; 23 char c = getchar(); 24 while( !isdigit(c) ){ 25 if ( c=='-' ) f = -1 ; 26 c = getchar(); 27 } 28 while( isdigit(c) ){ 29 x = ( (x<<1) + (x<<3) ) + c - '0' ; 30 c = getchar(); 31 } 32 x = x * f; 33 } 34 35 inline void pre(int No){ 36 memset( cnt, 0 ,sizeof cnt ); 37 int maxz = 0 ; 38 int ans = 0 ; 39 40 for(int i=(No-1)*t+1;i<=n;i++){ 41 cnt[a[i]] ++ ; 42 if( cnt[a[i]] > maxz || ( cnt[a[i]] == maxz && val[a[i]]<val[ans])) 43 ans = a[i] , maxz = cnt[a[i]]; 44 f[No][pos[i]] = ans ; 45 } 46 } 47 48 inline int query_cnt(int L,int R,int x){ 49 int k = U_b( all(v[x]),R) - L_b(all(v[x]),L); 50 return k ; 51 } 52 inline int query(int l,int r){ 53 int ans , maxz ; 54 ans = f[pos[l]+1][pos[r]-1]; 55 maxz = query_cnt ( l,r,ans ); 56 for(int i=l;i<=min(pos[l]*t,r);i++){ 57 int k = query_cnt( l ,r , a[i] ) ; 58 if( k > maxz || ( k == maxz && val[a[i]]<val[ans])) 59 ans = a[i] , maxz = k ; 60 } 61 if( pos[l] != pos[r] ){ 62 for( int i=(pos[r]-1)*t+1;i<=r;i++){ 63 int k = query_cnt( l ,r , a[i] ) ; 64 if( k > maxz || ( k == maxz && val[a[i]]<val[ans])) 65 ans = a[i] , maxz = k ; 66 } 67 } 68 return ans ; 69 } 70 int main() 71 { 72 read(n) ;t = 170 ; 73 for( int i=1;i<=n;i++) { 74 read(a[i]); 75 if( !Mp[a[i]]){ 76 Mp[a[i]] = i ; 77 val[i] = a[i]; 78 id ++ ; 79 } 80 a[i] = Mp[a[i]]; 81 v[a[i]].push_back(i); 82 } 83 84 for(int i=1;i<=n;i++) 85 pos[i] = (i-1)/t + 1; 86 for(int i=1;i<=pos[n];i++) 87 pre(i); 88 for(int i=1;i<=n;i++){ 89 read(l),read(r); 90 if( l > r ) swap(l,r); 91 printf("%d ",val[query(l,r)]); 92 } 93 return 0; 94 }
1 // luogu-judger-enable-o2 2 #include<cmath> 3 #include<vector> 4 #include<cctype> 5 #include<cstdio> 6 #include<algorithm> 7 #define all(x) x.begin(),x.end() 8 #define L_B lower_bound 9 typedef long long ll; 10 using namespace std; 11 const int N = 1e6+5; 12 const int M = 1e3+5; 13 int pos[N]; 14 int n,m,block ; 15 int a[N],add[M]; 16 vector<int> Vec[M] ; 17 18 template < class T > 19 inline void read( T& x ){ 20 x = 0 ; int f = 1 ; 21 char c = getchar() ; 22 while( !isdigit(c) ){ 23 if( c=='-' ) f = -1 ; 24 c = getchar() ; 25 } 26 while( isdigit(c) ){ 27 x = ( (x<<1) + (x<<3) ) + c-'0'; 28 c = getchar() ; 29 } 30 x = x * f ; 31 } 32 inline void reset(int No){ 33 Vec[No].clear(); 34 for(int i=(No-1)*block+1;i<=min(No*block,n);i++) 35 Vec[No].push_back(a[i]); 36 sort( Vec[No].begin(),Vec[No].end() ); 37 } 38 inline void Modify(int x,int y,int c){ 39 int p = pos[x] , q = pos[y] ; 40 if( p == q ){ 41 for(int i=x;i<=y;i++) 42 a[i] += c ; 43 reset(p); 44 }else{ 45 for(int i=x;i<=pos[x]*block;i++) 46 a[i] += c; 47 reset(pos[x]); 48 49 for(int i=(pos[y]-1)*block+1;i<=y;i++) 50 a[i] += c; 51 reset(pos[y]); 52 53 for(int i=pos[x]+1;i<=pos[y]-1;i++){ 54 add[i] += c ; 55 } 56 } 57 } 58 int Query(int x,int y,int C){ 59 60 //printf("### ( %d , %d) ### ",x,y); 61 int p = pos[x] ; 62 int q = pos[y] ; 63 int ans = 0 ; 64 if( p==q ){ 65 for(int i=x;i<=y;i++){ 66 if( a[i]+add[p] >= C ) 67 ans ++ ; 68 } 69 }else{ 70 //printf("$$$$$$ "); 71 for(int i=x;i<=p*block;i++){ 72 //printf("( %d , %d ) " ,i,a[i]+add[p]); 73 if( a[i]+add[p] >= C ) { 74 //printf("+++%d ",i); 75 ans++; 76 } 77 } 78 for(int i=(q-1)*block+1;i<=y;i++){ 79 //printf("( %d , %d ) " ,i,a[i]+add[p]); 80 if( a[i]+add[q] >= C ) { 81 //printf("+++%d ",i); 82 ans++; 83 } 84 } 85 for(int i=p+1;i<=q-1;i++){ 86 int tmp = ( Vec[i].end() - L_B(all(Vec[i]),C-add[i] ) ); 87 //printf("LB__%d, %d ",add[i],tmp); 88 ans += tmp; 89 } 90 } 91 return ans ; 92 } 93 int main() 94 { 95 read(n) , read(m) ; 96 block = (int)sqrt(n); 97 for(int i=1;i<=n;i++) { 98 read(a[i]); 99 pos[i] = (i-1)/block + 1 ; 100 Vec[pos[i]].push_back(a[i]); 101 } 102 103 for(int i=1;i<=pos[n];i++) 104 sort(all(Vec[i])); 105 106 char opt[5] ; 107 int l , r , C ; 108 for(int i=1;i<=m;i++){ 109 scanf("%s%d%d%d",opt,&l,&r,&C); 110 /* 111 for(int j=1;j<=n;j++){ 112 printf("%d%c",a[j],j==n?' ':' '); 113 } 114 for(int j=1;j<=pos[n];j++){ 115 printf("%d%c",add[j],j==pos[n]?' ':' '); 116 } 117 */ 118 if( opt[0] == 'M' ){ 119 Modify( l, r , C ); 120 }else { 121 printf("%d ",Query(l,r,C)); 122 } 123 } 124 return 0 ; 125 }