莫队，利用可以快速地通过一个问题的答案得到另一问题的答案这一特性，合理地组织问题的求解顺序，将已解决的问题帮助解决当前问题，来优化时间复杂度。典型用法：处理静态（
莫队，利用可以快速地通过一个问题的答案得到另一问题的答案这一特性，合理地组织问题的求解顺序，将已解决的问题帮助解决当前问题，来优化时间复杂度。典型用法：处理静态（无修改）离线区间查询问题。
莫队，利用可以快速地通过一个问题的答案得到另一问题的答案这一特性，合理地组织问题的求解顺序，将已解决的问题帮助解决当前问题，来优化时间复杂度。
典型用法：处理静态（无修改）离线区间查询问题。
线段树也是处理区间问题的一个有力工具，它和莫队算法各有特点：
线段树可以支持修改，并且单次操作时间复杂度一般为O(log)，支持在线，但是要求可以进行快速的区间合并操作，两个区间如不能快速合并（f(n)*O(log)>O(n)），则用线段树就没有什么实际价值了（暴力都比它块）
莫队算法可以解决某些线段树不能解决的静态离线问题，但它要求可以快速地从一个答案得到另一个答案。
对于区间问题，假如我们得到了区间[l,r]的答案，能通过它用O(1)的时间得到[l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案，那么我们将[l,r]看成二维平面上的点，两个点的距离用哈密顿距离表示，一个不错的想法是找到图的最小生成树，然后暴力推出一个点，其它点从它延伸过去就行了，时间复杂度是距离和加上暴力的那个点花的时间。
这道题除了上面的做法，还可以分块，如果分成n^0.5块，可以做到O(n^1.5)的复杂度。
做法是先将原颜色序列分成根号n块，然后将询问先按左端点排序，对于每一块的询问再按右端点排序（都是升序）。
每次计算一个左端点在一个块中的询问，先暴力这个区间的第一个询问，然后后面的每个询问从它前一个询问推（具体看代码）
时间复杂度可以这么看：
排序O(nlogn)
对于每个询问，它从前一个推过来，因为它们在同一块中，前端点改变最多O(n^0.5)次，有O(n)个询问，所以前端点变化O(n*n^0.5)次
对于每一段，后端点变化是O(n)的，而最多有O(n^0.5)段，所以后端点变化O(n^0.5*n)次
所以从一个[l,r]推到它四个相邻的点的次数是O(n^1.5)，而转移是O(1)的，所以总的复杂度是O(n^1.5)。
不论是分块还是最小生成树，都是想用最少的转移和最少的暴力将所有询问解决。
不会写最小生成树的做法。这个是分块，感谢proverbs
1 /************************************************************** 2 Problem: 2038 3 User: idy002 4 Language: C++ 5 Result: Accepted 6 Time:836 ms 7 Memory:2972 kb 8 ****************************************************************/ 9 10 #include 11 #include 12 #include 13 #define maxn 50010 14 using namespace std; 15 16 typedef long long lng; 17 18 lng gcd( lng a, lng b ) { 19 return b ? gcd(b,a%b) : a; 20 } 21 struct Query { 22 int l, r, idx; 23 lng ans[2]; 24 Query(){} 25 Query( int l, int r, int idx ) : l(l), r(r), idx(idx) {} 26 void set( lng sum ) { 27 lng len = (r-l+1); 28 lng a = sum, b = len*(len-1)/2; 29 lng c = gcd(a,b); 30 if( c ) { 31 ans[0] = a/c; 32 ans[1] = b/c; 33 } else { 34 ans[0] = 0; 35 ans[1] = 1; 36 } 37 } 38 }; 39 bool cmpl( const Query 41 } 42 bool cmpr( const Query 44 } 45 bool cmpid( const Query 47 } 48 struct Range { 49 int l, r; 50 Range(){} 51 Range( int l, int r ) : l(l), r(r) {} 52 }; 53 54 int n, m; 55 int clr[maxn], cnt[maxn]; 56 int tot; 57 Range rng[maxn]; 58 Query qry[maxn]; 59 60 void partition() { 61 int len = (int)ceil(sqrt(n)); 62 tot = n/len; 63 for( int i=1; i<=tot; i++ ) { 64 rng[i].l = rng[i-1].r+1; 65 rng[i].r = rng[i-1].r+len; 66 } 67 if( rng[tot].r < n ) { 68 tot++; 69 rng[tot].l = rng[tot-1].r+1; 70 rng[tot].r = n; 71 } 72 } 73 74 void work() { 75 sort( qry+1, qry+1+m, cmpl ); 76 int s, t; 77 lng sum; 78 s = t = 1; 79 for( int i=1; i<=tot; i++ ) { 80 while( s<=m 81 while( t<=m 83 sort( qry+s, qry+t, cmpr ); 84 sum = 0; 85 for( int j=qry[s].l; j<=qry[s].r; j++ ) 86 sum += cnt[clr[j]]++; 87 qry[s].set( sum ); 88 for( int q=s+1; q qry[q-1].r ) { // ( ) [ ] 90 for( int j=qry[q-1].l; j<=qry[q-1].r; j++ ) 91 cnt[clr[j]]--; 92 sum = 0; 93 for( int j=qry[q].l; j<=qry[q].r; j++ ) 94 sum += cnt[clr[j]]++; 95 } else if( qry[q].l <= qry[q-1].l ) { // [ ( ) ] 96 for( int j=qry[q].l; j
nbut 1457:
询问一个区间中每种颜色的数量的立方和
1 #include 2 #include 3 #include 4 #include 5 #define maxn 100010 6 using namespace std; 7 8 typedef long long lng; 9 10 struct Qu { 11 int l, r, id; 12 }; 13 bool cmpl( const Qu 15 } 16 bool cmpr( const Qu 18 } 19 20 21 int n, m; 22 int idx[maxn], itot; 23 int clr[maxn]; 24 lng cnt[maxn]; 25 int lx[maxn], rx[maxn], stot; 26 Qu qu[maxn]; 27 lng ans[maxn]; 28 29 30 void partition() { 31 int len = (int)ceil(sqrt(n)); 32 stot = n/len; 33 rx[0] = 0; 34 for( int i=1; i<=stot; i++ ) { 35 lx[i] = rx[i-1]+1; 36 rx[i] = rx[i-1]+len; 37 } 38 if( rx[stot]!=n ) { 39 stot++; 40 lx[stot] = rx[stot-1]+1; 41 rx[stot] = n; 42 } 43 } 44 void makeid() { 45 sort( idx+1, idx+1+n ); 46 int tot = unique( idx+1, idx+1+n ) - idx; 47 for( int i=1; i<=n; i++ ) 48 clr[i] = lower_bound( idx+1, idx+tot, clr[i] ) - idx; 49 } 50 lng cube( lng a ) { 51 return a*a*a; 52 } 53 void update( lng 55 cnt[c] += delta; 56 sum += cube(cnt[c]); 57 } 58 void work() { 59 sort( qu+1, qu+1+m, cmpl ); 60 for( int i=1,s=1,t=1; i<=stot; i++ ) { 61 memset( cnt, 0, sizeof(cnt) ); 62 while( s<=m 63 while( t<=m 64 sort( qu+s, qu+t, cmpr ); 65 66 lng sum = 0; 67 for( int j=qu[s].l; j<=qu[s].r; j++ ) 68 update( sum, clr[j], +1 ); 69 ans[qu[s].id] = sum; 70 for( int q=s+1; q
