Melancholy
Time Limit: 10 Sec Memory Limit: 256 MB
Description
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 3
Sample 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
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef unsigned int u32; const int ONE = ;
const int MOD = 1e9 + ;
const u32 INF = 4294967295u; int n, Q;
int k;
struct point
{
u32 d, v;
}a[ONE], L, R;
bool cmp(const point &a, const point &b) {return a.d < b.d;} struct power
{
u32 val[];
friend power operator +(power a, power b)
{
power c;
for(int i = ; i <= ; i++) c.val[i] = a.val[i] + b.val[i];
for(int i = ; i <= ; i++)
for(int j = ; j < i; j++)
c.val[i] += a.val[j] * b.val[i - j];
return c;
}
}Node[ONE], A[], Ans; struct Min
{
u32 val, pos;
friend Min operator +(Min a, Min b)
{
Min c = (Min){INF, };
if(a.val < c.val) c = a;
if(b.val < c.val) c = b;
return c;
}
}Val[ONE], res_min; int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} namespace Seg
{
void Build(int i, int l, int r)
{
Val[i] = (Min){INF, };
for(int j = ; j <= ; j++) Node[i].val[j] = ;
if(l == r)
{
Node[i].val[] = a[l].v;
Val[i] = (Min){a[l].v, l};
return;
}
int mid = l + r >> ;
Build(i << , l, mid); Build(i << | , mid + , r);
Node[i] = Node[i << ] + Node[i << | ];
Val[i] = Val[i << ] + Val[i << | ];
} void Find(int i, int l, int r, int L, int R)
{
if(L > R) return;
if(L <= l && r <= R)
{
res_min = res_min + Val[i];
return;
}
int mid = l + r >> ;
if(L <= mid) Find(i << , l, mid, L, R);
if(mid + <= R) Find(i << | , mid + , r, L, R);
} void Query(int i, int l, int r, int L, int R, int opt)
{
if(L > R) return;
if(L <= l && r <= R)
{
A[opt] = A[opt] + Node[i];
return;
}
int mid = l + r >> ;
if(L <= mid) Query(i << , l, mid, L, R, opt);
if(mid + <= R) Query(i << | , mid + , r, L, R, opt);
}
} void Deal(int k)
{
int Left = lower_bound(a + , a + n + , L, cmp) - a;
int Right = upper_bound(a + , a + n + , R, cmp) - a - ;
if(Left >= Right) {printf("0\n"); return;} res_min = (Min){INF, };
Seg::Find(, , n, Left, Right); for(int i = ; i <= ; i++) A[].val[i] = A[].val[i] = ;
Seg::Query(, , n, Left, res_min.pos - , );
Seg::Query(, , n, res_min.pos + , Right, ); Ans = A[] + A[];
for(u32 i = ; i <= k; i++) Ans.val[k] *= i;
printf("%u\n", Ans.val[k]);
} int main()
{
n = get(); Q = get();
for(int i = ; i <= n; i++) a[i].d = get();
for(int i = ; i <= n; i++) a[i].v = get();
sort(a + , a + n + , cmp); Seg::Build(, , n); while(Q--)
{
L.d = get(), R.d = get(), k = get();
Deal(k);
}
}