离线线段树 SPOJ - GSS2【Can you answer these queries II】
https://cn.vjudge.net/contest/304248#problem/H
题意
给定 n 个整数（有负数）和 m 次操作，令 (q(l,r)) 为 l 到 r 之间所有数去重后的和，每次询问 (max(q(x,y)[li leq x leq y leq ri])) 。
分析
我实在不知道怎么用莫队做，理论上是可以，但怎么 add() 和 del() 我写不出来。
然后我就去搜了题解，然后没有一个用莫队的，我惊了...
不过和莫队有共通点（离线），边更新边查询。
需要两个懒惰标记，第一个用来正常的区间更新操作的；而第二个是用来更新最优解的，比如一个区间中下传了-5，但是在他的左儿子中有个懒惰标记为5，对于他的左儿子来说，直接加5才是最优解。
也算是又学了一招（-……-）
代码
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5+5;
const int nn = 1e5;
int n, m;
ll a[maxn];
int vis[maxn<<1]; // 负数要翻正（*2），用来记录上一次出现值x的位置
ll res[maxn];
struct Tree {
ll sum, lazy, ans, prelazy;
// sum 记录区间去重和的最大后缀和
// lazy 记录下传的值
// ans 记录区间去重和的最大值
// prelazy 记录下传的最大值
}tree[maxn<<2];
struct node{
int l, r, id;
bool operator < (const node &a) const {
return r < a.r; // 按区间右端点进行离线排序
}
}Q[maxn];
void pushup(int rt) { // 常规更新
tree[rt].sum = max(tree[2*rt].sum, tree[2*rt+1].sum);
tree[rt].ans = max(tree[2*rt].ans, tree[2*rt+1].ans);
}
void pushdown(int rt) { // 懒惰标记更新
if(tree[rt].lazy || tree[rt].prelazy) { // 根据父节点更新子节点的各项值
tree[2*rt].prelazy = max(tree[2*rt].prelazy, tree[2*rt].lazy + tree[rt].prelazy);
tree[2*rt+1].prelazy = max(tree[2*rt+1].prelazy, tree[2*rt+1].lazy + tree[rt].prelazy);
tree[2*rt].ans = max(tree[2*rt].ans, tree[2*rt].sum + tree[rt].prelazy);
tree[2*rt+1].ans = max(tree[2*rt+1].ans, tree[2*rt+1].sum + tree[rt].prelazy);
tree[2*rt].lazy += tree[rt].lazy;
tree[2*rt+1].lazy += tree[rt].lazy;
tree[2*rt].sum += tree[rt].lazy;
tree[2*rt+1].sum += tree[rt].lazy;
tree[rt].lazy = tree[rt].prelazy = 0; // 标记还原
}
}
void build(int l, int r, int rt) {
tree[rt].sum = tree[rt].lazy = tree[rt].prelazy = tree[rt].ans = 0;
if(l == r) {
return ;
}
int mid = (l+r) >> 1;
build(l, mid, 2*rt);
build(mid+1, r, 2*rt+1);
pushup(rt);
}
void update(int L, int R, int l, int r, int rt, ll val) {
if(L <= l && r <= R) {
tree[rt].sum += val;
tree[rt].lazy += val; // 区间更新需要更新懒惰标记
tree[rt].ans = max(tree[rt].ans, tree[rt].sum);
tree[rt].prelazy = max(tree[rt].prelazy, tree[rt].lazy); // 取最大
return ;
}
pushdown(rt);
int mid = (l+r) >> 1;
if(L <= mid) {
update(L, R, l, mid, 2*rt, val);
}
if(R > mid) {
update(L, R, mid+1, r, 2*rt+1, val);
}
pushup(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return tree[rt].ans;
}
pushdown(rt);
ll ans = (-1ll)*maxn*maxn; // 因为 ans 有可能为负数（不过应该是没有影响的，0 也可以）
int mid = (l+r) >> 1;
if(L <= mid) {
ans = max(ans, query(L, R, l, mid, 2*rt));
}
if(R > mid) {
ans = max(ans, query(L, R, mid+1, r, 2*rt+1));
}
return ans;
}
int main() {
// fopen("in.txt", "r", stdin);
// fopen("out.txt", "w", stdout);
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
build(1, n, 1);
scanf("%d", &m);
for(int i = 1; i <= m; i++) {
scanf("%d%d", &Q[i].l, &Q[i].r);
Q[i].id = i;
}
sort(Q+1, Q+1+m);
int cnt = 1;
for(int i = 1; i <= n; i++) {
update(vis[a[i]+nn]+1, i, 1, n, 1, a[i]);
// L = 上一次出现该值的位置 + 1
// R = 当前位置 i
vis[a[i]+nn] = i;
while(cnt <= m && Q[cnt].r == i) {
// 当 Q[cnt].r == i 时，后续操作与当前查询无关，直接查询
res[Q[cnt].id] = query(Q[cnt].l, Q[cnt].r, 1, n, 1);
cnt ++;
}
}
for(int i = 1; i <= m; i++) {
printf("%lld
", res[i]);
}
return 0;
}