整体二分板题,没啥好讲的…注意是个环…还有所有贡献会爆longlong,那么只要在加之前判断一下有没有达到需要的值就行了…

CODE

#include <set>

#include <queue>

#include <cctype>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

    char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;

    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 300005;

vector<int>vec[MAXN];

int n, m, k, O[MAXN], L[MAXN], R[MAXN], A[MAXN], ans[MAXN];

struct query { int p, id; }q[MAXN], tmp[MAXN];

LL T[MAXN], val[MAXN];

inline void upd(int x, int val) {

	while(x <= m) T[x] += val, x += x&-x;

}

inline LL qsum(int x) { LL re = 0;

	while(x) re += T[x], x -= x&-x;

	return re;

}

inline void calc(int ql, int qr, int l, int r) {

	for(int i = ql; i <= qr; ++i) val[i] = 0;

	for(int i = l; i <= r; ++i) {

		upd(L[i], A[i]), upd(R[i]+1, -A[i]);

		if(L[i] > R[i]) upd(1, A[i]);

	}

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

		for(int j = 0, siz = vec[q[i].id].size(); j < siz; ++j) {

			val[i] += qsum(vec[q[i].id][j]);

			if(val[i] >= q[i].p) break;

		}

	for(int i = l; i <= r; ++i) {

		upd(L[i], -A[i]), upd(R[i]+1, A[i]);

		if(L[i] > R[i]) upd(1, -A[i]);

	}

}

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

	if(qr < ql) return;

	if(vl == vr) { for(int i = ql; i <= qr; ++i) ans[q[i].id] = vl; return; }

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

	calc(ql, qr, vl, vmid);

	int st = ql, ed = qr;

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

		if(q[i].p <= val[i]) tmp[st++] = q[i];

		else q[i].p -= val[i], tmp[ed--] = q[i];

	for(int i = ql; i <= qr; ++i) q[i] = tmp[i];

	solve(ql, st-1, vl, vmid);

	solve(ed+1, qr, vmid+1, vr);

}

int main () {

	read(n), read(m);

	for(int i = 1, x; i <= m; ++i) read(x), vec[x].push_back(i);

	for(int i = 1; i <= n; ++i) read(q[i].p), q[i].id = i;

	read(k);

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

		read(L[i]), read(R[i]), read(A[i]);

	solve(1, n, 1, k+1);

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

		if(ans[i] <= k) printf("%d\n", ans[i]);

		else puts("NIE");

}

巴特西

BZOJ 2527 [Poi2011]Meteors (整体二分+树状数组)

CODE

最新文章

热门文章