Brief description:
给定一个长度为 M 的环，每个位置属于 N 个国家之一。
有 K 个事件依次进行。每个事件形如 l, r, d 。
表示环上的一段连续区间中，每个位置的数 +d 。。。
国家 i 希望自己所属区域的数的和 >= Pi。。
返回每个国家达到各自需求的时间。如果达不到输出 NIE。
Analysis:
cdq 分治。）
void cdq(const VI I, int l, int r) // 表示确定 I 中的事件，哪些处在 [l, r) 的左半区间，哪些处在右半区间、递归处理。 // 先生效所有属于左半边的操作，此时可以判断每个事件的归属。。 // 之后需要先递归右半边，把操作复原后递归左半边、、否则需要用一个额外的容器记录增量。
。。。对时间二分。。整体处理询问。。
//}/* .................................................................................................................................. */
const int N = int(3e5) + 9;
VI L[N]; LL A[N]; int ans[N];
int n, m, k;
namespace BIT{
typedef LL intt;
intt C[N];
void Add(int x, int d){
for (;x<=n;x+=low_bit(x)) C[x] += d;
}
intt Sum(int x){
intt z = 0; for (;x;x^=low_bit(x)) z += C[x];
return z;
}
void Add(int l, int r, int d){
Add(l, d); Add(r+1, -d);
}
void Init(){
//fill(C+1, C+n+1, 0);
}
} //using namespace BIT;
struct Op{
int l, r, d;
void in(){
RD(l, r, d);
}
void Add(){
if (l <= r) BIT::Add(l, r, d);
else BIT::Add(l, n, d), BIT::Add(1, r, d);
}
void Del(){
if (l <= r) BIT::Add(l, r, -d);
else BIT::Add(l, n, -d), BIT::Add(1, r, -d);
}
} op[N];
void cdq(const VI I, int l, int r){
if (I.empty()) return;
if (l + 1 == r){
ECH(i, I) ans[*i] = l;
}
else{
int m = l + r >> 1;
FOR(i, l, m) op[i].Add();
VI Il, Ir; ECH(i, I){
LL a = 0; ECH(ii, L[*i]){
a += BIT::Sum(*ii);
if (a >= A[*i]) break;
}
if (a < A[*i]){
Ir.PB(*i);
}
else{
Il.PB(*i);
}
}
cdq(Ir, m, r); FOR(i, l, m) op[i].Del();
cdq(Il, l, m);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(m, n); REP_1(i, n) L[RD()-1].PB(i);
VI I; REP(i, m) RD(A[i]), I.PB(i);
RD(k); REP(i, k) op[i].in();
cdq(I, 0, k+1);
REP(i, m){
if (ans[i] == k) puts("NIE");
else OT(ans[i]+1);
}
}
http://www.lydsy.com/JudgeOnline/problem.php?id=2527
http://main.edu.pl/en/archive/oi/18/met
References:
http://www.cnblogs.com/zig-zag/archive/2013/04/29/3051212.html
