2013-04-12 17:41:01Morris
[NPSC][歸併樹] a656. E. 胖胖天天天胖
內容 ：
胖胖天，天天胖！
身為一個專業飲料愛好者，胖胖天經常研究飲料相關的問題並樂此不疲。現在有許多飲料在胖胖天面前排成一排，每個飲料都有其購買的成本。他想從特定區段中挑出盡量多瓶飲料，使得總成本不超過他錢包裡的錢，請問他最多可以挑幾瓶呢？
聰明的胖胖天已經先寫了一個程式來輔助他喝遍天下的飲料，但謹慎的他還是請你也寫一份來確認他寫的程式是否正確。但為了肉眼比對方便，聰明的胖胖天決定比較結果的雜湊值就好，也就是假設對每次詢問所能購買的瓶數依序為p1, p2, ..., pk，則我們定義其雜湊值為(p1 + 1)^(p2 + 2)^...^(pk + k)，其中^代表xor 運算。
輸入說明
：
輸入檔的第一行有一個正整數T (T<=514)，表示接下來總共有幾筆測試資料。
每一筆測試資料第一行有兩個正整數N,Q (N,Q<=105)，代表總共有N 瓶飲料，胖胖天將問你Q 個問題。飲料編號由左到右為1, 2, ...,N。下一行有N 個非負整數，依序代表每瓶飲料的購買成本，飲料的成本不會超過104。再接下來有Q 行，每行有三個整數L,R, S (1<=L<=R<=N, 0<=S<=109)，代表胖胖天想問你如果他錢包裡剛好有S 元，他最多可以買幾瓶編號在L 到R 之間的飲料呢？
輸出說明
：
對於每筆測試資料，請輸出其對應的雜湊值。若對雜湊值之運算有所疑惑可以參考題目B 所附之程式碼。
範例輸入 ：
2 3 1 5 1 4 1 3 5 5 2 1 1 5 1 5 2 5 5 1 4 5
範例輸出 ：
3 6
提示
：
出處
：
NPSC 2012 高中組決賽
(管理：xavier13540)
题目简述：
在指定区间抓取总合不大于 S 的元素集合，而集合大小越大越好
题目分析：
对于区间[L，R]很明显地，从小排到大，依序挑入即可，照贪婪的思路。
但没办法对每个询问区间进行排序，因此使用归并树。
将合并排序的每个过程记录下来，然后二分边界数值。
小心，等价的边界数值要特别处理。
/*********************************************************/题目简述：
在指定区间抓取总合不大于 S 的元素集合，而集合大小越大越好
题目分析：
对于区间[L，R]很明显地，从小排到大，依序挑入即可，照贪婪的思路。
但没办法对每个询问区间进行排序，因此使用归并树。
将合并排序的每个过程记录下来，然后二分边界数值。
小心，等价的边界数值要特别处理。
/* Problem: a656 "E. 胖胖天天天胖" from NPSC 2012 高中組決賽*/
/* Language: CPP (3083 Bytes) */
/* Result: AC(3.7s, 10.8MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-04-12 09:00:55 */
/********************************************************/
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
short ST[20][100010];
int AST[20][100010];
void build(int dep, int l, int r) {
if(l < r) {
int m = (l+r)/2, i;
memcpy(ST[dep+1]+l, ST[dep]+l, (r-l+1)*2);
build(dep+1, l, m);
build(dep+1, m+1, r);
int idx1 = l, idx2 = m+1, top = l, tmp = 0;
while(idx1 <= m && idx2 <= r) {
if(ST[dep+1][idx1] < ST[dep+1][idx2])
ST[dep][top] = ST[dep+1][idx1++];
else
ST[dep][top] = ST[dep+1][idx2++];
tmp += ST[dep][top];
AST[dep][top++] = tmp;
}
while(idx1 <= m) {
ST[dep][top] = ST[dep+1][idx1++];
tmp += ST[dep][top];
AST[dep][top++] = tmp;
}
while(idx2 <= r) {
ST[dep][top] = ST[dep+1][idx2++];
tmp += ST[dep][top];
AST[dep][top++] = tmp;
}
}
if(l == r)
AST[dep][l] = ST[dep][l];
}
int L, R, S;
int key, Count, cost, same;
void query(int dep, int l, int r, int ql, int qr) {
if(cost > S) return ;
if(l == ql && r == qr) {
int ff = upper_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
int gg = lower_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
same += ff-gg;
if(gg) {
Count += gg;
cost += AST[dep][gg+l-1];
}
return;
}
int m = (l+r)/2;
if(m >= qr)
query(dep+1, l, m, ql, qr);
else if(m < ql)
query(dep+1, m+1, r, ql, qr);
else {
query(dep+1, l, m, ql, m);
query(dep+1, m+1, r, m+1, qr);
}
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int t;
int n, q, i, j;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &q);
for(i = 1; i <= n; i++) {
//scanf("%d", &ST[0][i]);
ReadInt(&j);
ST[0][i] = j;
}
build(0, 1, n);
int ans = 0;
ST[0][0] = 0;
for(i = 1; i <= q; i++) {
//scanf("%d %d %d", &L, &R, &S);
ReadInt(&L);
ReadInt(&R);
ReadInt(&S);
int l = 0, r = n, m;
int x = 0;
while(l <= r) {
m = (l+r)/2;
key = ST[0][m], Count = 0, cost = 0, same = 0;
query(0, 1, n, L, R);
if(cost <= S) {
l = m+1;
if(key)
Count += min((S-cost)/key, same);
if(Count > x) x = Count;
} else
r = m-1;
}
ans ^= x+i;
}
printf("%d\n", ans);
}
return 0;
}