laekov

全局二分+树状数组，其实还是比较水。

比较坑的一点是直接求和会暴long long。如果≥Pi了要直接break掉。好坑啊。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

using namespace std; 

int _d_;

#define readInt(_x_) { \

int& _s_ = (_x_ = 0); \

while (!isdigit(_d_ = getchar())); \

while (_s_ = (_s_ << 3) + (_s_ << 1) + _d_ - 48, isdigit(_d_ = getchar())); \

}

typedef long long dint;

const int maxn = 300009;

struct node {

int v;

node *next;

};

struct rain {

int l, r, a;

};

struct bintree {

dint t[maxn];

int n;

bintree() {

memset(t, 0, sizeof(t));

}

void chg(int p, int v) {

for (; p <= n; p += (p & -p))

t[p] += v;

}

dint qry(int p) {

dint s = 0;

for (; p; p -= (p & -p))

s += t[p];

return s;

}

};

int n, m, t, ans[maxn], o[maxn], w[maxn];

bool dr[maxn];

rain a[maxn];

node *head[maxn], *np;

bintree bt;

void binTest(int vl, int vr, int ql, int qr) {

if (ql >= qr)

return;

else if (vl + 1 == vr) {

for (int i = ql; i < qr; ++ i)

ans[o[i]] = vl;

}

else {

int vm = (vl + vr) >> 1;

for (int i = vl; i < vm; ++ i)

if (a[i]. l <= a[i]. r) {

bt. chg(a[i]. l, a[i]. a);

bt. chg(a[i]. r + 1, -a[i]. a);

}

else {

bt. chg(1, a[i]. a);

bt. chg(a[i]. r + 1, -a[i]. a);

bt. chg(a[i]. l, a[i]. a);

}

for (int i = ql; i < qr; ++ i) {

dint sc = 0;

for (node* j = head[o[i]]; j && sc < w[o[i]]; j = j-> next)

sc += bt. qry(j-> v);

if (sc >= w[o[i]])

dr[i] = 0;

else

dr[i] = 1;

}

int nl = ql, nr = qr - 1;

while (nl <= nr) {

for (; nl < nr && !dr[nl]; ++ nl);

for (; nl < nr && dr[nr]; -- nr);

if (nl <= nr) {

swap(o[nl], o[nr]);

swap(dr[nl], dr[nr]);

++ nl;

-- nr;

}

}

for (nl = ql; nl < qr && !dr[nl]; ++ nl);

binTest(vm, vr, nl, qr);

for (int i = vl; i < vm; ++ i)

if (a[i]. l <= a[i]. r) {

bt. chg(a[i]. l, -a[i]. a);

bt. chg(a[i]. r + 1, a[i]. a);

}

else {

bt. chg(1, -a[i]. a);

bt. chg(a[i]. r + 1, a[i]. a);

bt. chg(a[i]. l, -a[i]. a);

}

binTest(vl, vm, ql, nl);

}

}

int main() {

#ifndef ONLINE_JUDGE

//freopen("in.txt", "r", stdin);

#endif

readInt(n);

readInt(m);

bt. n = m + 1;

memset(head, 0, sizeof(head));

np = new node[m];

for (int i = 1; i <= m; ++ i) {

int v;

readInt(v);

np-> v = i;

np-> next = head[v];

head[v] = np ++;

}

for (int i = 1; i <= n; ++ i) {

readInt(w[i]);

o[i - 1] = i;

}

readInt(t);

for (int i = 0; i < t; ++ i) {

readInt(a[i]. l);

readInt(a[i]. r);

readInt(a[i]. a);

}

a[t]. l = a[t]. r = 1;

a[t]. a = 0;

binTest(0, t + 1, 0, n);

for (int i = 1; i <= n; ++ i)

if (ans[i] == t)

puts("NIE");

else

printf("%d\n", ans[i] + 1);

}