Melancholy
Time Limit: 10 Sec Memory Limit: 256 MBDescription
DX3906星系，Melancholy星上，我在勘测这里的地质情况。
我把这些天来已探测到的区域分为N组，并用二元组(D,V)对每一组进行标记：其中D为区域的相对距离，V为内部地质元素的相对丰富程度 在我的日程安排表上有Q项指派的计划。 每项计划的形式是类似的，都是“对相对距离D在[L,R]之间的区域进行进一步的勘测，并在其中有次序地挑出K块区域的样本进行研究。”采集这K块的样品 后，接下来在实验中，它们的研究价值即为这K块区域地质相对丰富程度V的乘积。 我对这Q项计划都进行了评估：一项计划的评估值P为所有可能选取情况的研究价值之和。 但是由于仪器的原因，在一次勘测中，这其中V最小的区域永远不会被选取。 现在我只想知道这Q项计划的评估值对2^32取模后的值，特殊地，如果没有K块区域可供选择， 评估值为0。Input
第一行给出两个整数，区域数N与计划数Q。
第二行给出N个整数，代表每一块区域的相对距离D。 第三行给出N个整数，代表每一块区域的内部地质元素的相对丰富程度V。 接下来的Q行，每一行3个整数，代表相对距离的限制L,R，以及选取的块数K。Output
输出包括Q行，每一行一个整数，代表这项计划的评估值对2^32取模后的值。
Sample Input
5 3
5 4 7 2 6 1 4 5 3 2 6 7 1 2 6 2 1 8 3Sample Output
5
52 924 
HINT
Main idea
查询D在[L, R]中的元素，去掉最小的L值之后，任意k几个相乘的和。
Solution
首先，我们可以按照D排序一下，然后调出D在[L,R]的元素，显然是连续的一段。
然后我们再记录一下最小值L，以及最小值L所在的位置。这样在线段树上区间查询一下，就可以得到最小值的pos。
那么我们就将询问化成了，查询两个区间的信息并且合并。
问题在于如何合并。
我们对于线段树上的每个节点，记录一下val[i]表示选了i个乘起来的和。
那么两个区间合并起来时，val[i] = ΣA.val[j] * B.val[i - j]，根据乘法分配律可以看出。
比如我们左区间选了2个的答案形如：x1·x2 + y1·y2，右区间选了1个的答案形如：z1 + z2。
那么合并之后的区间 选了3个答案形如：x1·x2·z1 + x1·x2·z2 + y1·y2·z2+ y1·y2·z2，显然就是两个乘起来，并且不漏状态。
这样就可以得到答案啦。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef unsigned int u32; 10 11 const int ONE = 1000005; 12 const int MOD = 1e9 + 7; 13 const u32 INF = 4294967295u; 14 15 int n, Q; 16 int k; 17 struct point 18 { 19 u32 d, v; 20 }a[ONE], L, R; 21 bool cmp(const point &a, const point &b) { return a.d < b.d;} 22 23 struct power 24 { 25 u32 val[7]; 26 friend power operator +(power a, power b) 27 { 28 power c; 29 for(int i = 1; i <= 6; i++) c.val[i] = a.val[i] + b.val[i]; 30 for(int i = 1; i <= 6; i++) 31 for(int j = 1; j < i; j++) 32 c.val[i] += a.val[j] * b.val[i - j]; 33 return c; 34 } 35 }Node[ONE], A[3], Ans; 36 37 struct Min 38 { 39 u32 val, pos; 40 friend Min operator +(Min a, Min b) 41 { 42 Min c = (Min){INF, 0}; 43 if(a.val < c.val) c = a; 44 if(b.val < c.val) c = b; 45 return c; 46 } 47 }Val[ONE], res_min; 48 49 int get() 50 { 51 int res=1,Q=1; char c; 52 while( (c=getchar())<48 || c>57) 53 if(c=='-')Q=-1; 54 if(Q) res=c-48; 55 while((c=getchar())>=48 && c<=57) 56 res=res*10+c-48; 57 return res*Q; 58 } 59 60 namespace Seg 61 { 62 void Build(int i, int l, int r) 63 { 64 Val[i] = (Min){INF, 0}; 65 for(int j = 1; j <= 6; j++) Node[i].val[j] = 0; 66 if(l == r) 67 { 68 Node[i].val[1] = a[l].v; 69 Val[i] = (Min){a[l].v, l}; 70 return; 71 } 72 int mid = l + r >> 1; 73 Build(i << 1, l, mid); Build(i << 1 | 1, mid + 1, r); 74 Node[i] = Node[i << 1] + Node[i << 1 | 1]; 75 Val[i] = Val[i << 1] + Val[i << 1 | 1]; 76 } 77 78 void Find(int i, int l, int r, int L, int R) 79 { 80 if(L > R) return; 81 if(L <= l && r <= R) 82 { 83 res_min = res_min + Val[i]; 84 return; 85 } 86 int mid = l + r >> 1; 87 if(L <= mid) Find(i << 1, l, mid, L, R); 88 if(mid + 1 <= R) Find(i << 1 | 1, mid + 1, r, L, R); 89 } 90 91 void Query(int i, int l, int r, int L, int R, int opt) 92 { 93 if(L > R) return; 94 if(L <= l && r <= R) 95 { 96 A[opt] = A[opt] + Node[i]; 97 return; 98 } 99 int mid = l + r >> 1;100 if(L <= mid) Query(i << 1, l, mid, L, R, opt);101 if(mid + 1 <= R) Query(i << 1 | 1, mid + 1, r, L, R, opt);102 }103 }104 105 void Deal(int k)106 {107 int Left = lower_bound(a + 1, a + n + 1, L, cmp) - a;108 int Right = upper_bound(a + 1, a + n + 1, R, cmp) - a - 1;109 if(Left >= Right) {printf("0\n"); return;}110 111 res_min = (Min){INF, 0};112 Seg::Find(1, 1, n, Left, Right);113 114 for(int i = 1; i <= 6; i++) A[1].val[i] = A[2].val[i] = 0;115 Seg::Query(1, 1, n, Left, res_min.pos - 1, 1);116 Seg::Query(1, 1, n, res_min.pos + 1, Right, 2);117 118 Ans = A[1] + A[2];119 for(u32 i = 1; i <= k; i++) Ans.val[k] *= i;120 printf("%u\n", Ans.val[k]);121 }122 123 int main()124 {125 n = get(); Q = get();126 for(int i = 1; i <= n; i++) a[i].d = get();127 for(int i = 1; i <= n; i++) a[i].v = get();128 sort(a + 1, a + n + 1, cmp);129 130 Seg::Build(1, 1, n);131 132 while(Q--)133 {134 L.d = get(), R.d = get(), k = get();135 Deal(k);136 }137 }