bzoj2482.cc

#include #include #include #include

using namespace std;

const int max_buf = 4567; char buf[max_buf], *bufb(buf), *bufe(bufb + 1); #define readBuf() {
if (++ bufb == bufe)
bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin);
} #define readInt(x) {
register int s(0);
register bool nag(0);
do {
readBuf();
} while (!isdigit(*bufb) && *bufb != ‘-’);
if (*bufb == ‘-’) {
nag = 1;
readBuf();
}
do {
s = s * 10 + *bufb - 48;
readBuf();
} while (isdigit(*bufb));
if (nag)
x = -s;
else
x = s;
}

typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)

struct seg { dint s, v, a, z; int l, r; seg *ls, *rs; }; struct query { int l, r, i; }; inline bool operator <(const query& a, const query& b) { return a. r < b. r; }

typedef pair <dint, dint> dpr;

const int maxn = 100009;

int n, m, a[maxn], rl[maxn « 1]; dint ans[maxn]; seg slst[maxn * 3], *sp(slst), *rt; query q[maxn];

#define midp(p) ((p->l+p->r)»1) inline void update(seg* p) { p-> v = max(p-> ls-> v, p-> rs-> v); p-> s = max(p-> s, p-> v); }

#define grabAdd(p, a, z) {
p-> z = max(p-> z, p-> a + z);
p-> a += a;
p-> s = max(p-> s, p-> v + z);
p-> v += a;
} void pushDown(seg* p) { if (p-> l + 1 < p-> r) { grabAdd(p-> ls, p-> a, p-> z); grabAdd(p-> rs, p-> a, p-> z); p-> a = p-> z = 0; } }

inline seg* sgtBuild(int l, int r) { seg p(sp ++); p-> s = p-> v = p-> a = p-> z = 0; p-> l = l; p-> r = r; if (l + 1 < r) { p-> ls = sgtBuild(l, midp(p)); p-> rs = sgtBuild(midp(p), r); } return p; } inline void sgtChg(seg p, int l, int r, int a) { pushDown(p); if (p-> l == l && p-> r == r) { grabAdd(p, a, max(a, 0)); } else { if (r <= midp(p)) sgtChg(p-> ls, l, r, a); else if (l >= midp(p)) sgtChg(p-> rs, l, r, a); else { sgtChg(p-> ls, l, midp(p), a); sgtChg(p-> rs, midp(p), r, a); } update(p); } } inline dint sgtQry(seg* p, int l, int r) { pushDown(p); if (p-> l == l && p-> r == r) return p-> s; else { if (r <= midp(p)) return sgtQry(p-> ls, l, r); else if (l >= midp(p)) return sgtQry(p-> rs, l, r); else return max(sgtQry(p-> ls, l, midp(p)), sgtQry(p-> rs, midp(p), r)); } }

int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif

readInt(n);
for (int i = 1; i <= n; ++ i)
	readInt(a[i]);
readInt(m);
for (int i = 0; i < m; ++ i) {
	readInt(q[i]. l);
	readInt(q[i]. r);
	q[i]. i = i;
}
sort(q, q + m);
rt = sgtBuild(1, n + 1);
memset(rl, 0, sizeof(rl));
for (int i = 1, j = 0; j < m; ++ i) {
	sgtChg(rt, rl[a[i] + maxn] + 1, i + 1, a[i]);
	rl[a[i] + maxn] = i;
	for (; j < m && q[j]. r == i; ++ j)
		ans[q[j]. i] = sgtQry(rt, q[j]. l, q[j]. r + 1);
}
for (int i = 0; i < m; ++ i)
	printf(lld "\n", ans[i]);

}

Comments