题解 SP1557 GSS2 - Can you answer these queries II
FutaRimeWoawaSete · · 题解
由于每个相同的数只能出现一次，是一个经典的扫描线问题的暗示。
考虑扫描线，扫描
显然维护每个数的
同时维护每个区间的历史最大值即可维护答案。
#include "bits/stdc++.h"
using namespace std;
const int Len = 5e5 + 5 , Inf = 1e9;
int n,m,a[Len];
#define ls(p) p << 1
#define rs(p) p << 1 | 1
struct node
{
long long sum;
int maxa,maxb,se,cnt;
int add_a,add_a1,add_b,add_b1;//最大值的 tag，max 的上一次到这一次的 maxtag，其它值的 tag，其它数这一次到上一次的 maxtag
}t[Len << 2];
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void write(long long x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void push_up(int x)
{
t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
t[x].maxa = max(t[ls(x)].maxa , t[rs(x)].maxa);
t[x].maxb = max(t[ls(x)].maxb , t[rs(x)].maxb);
if(t[ls(x)].maxa == t[rs(x)].maxa)
{
t[x].se = max(t[ls(x)].se , t[rs(x)].se);
t[x].cnt = t[ls(x)].cnt + t[rs(x)].cnt;
}
if(t[ls(x)].maxa > t[rs(x)].maxa)
{
t[x].se = max(t[rs(x)].maxa , t[ls(x)].se);
t[x].cnt = t[ls(x)].cnt;
}
if(t[ls(x)].maxa < t[rs(x)].maxa)
{
t[x].se = max(t[ls(x)].maxa , t[rs(x)].se);
t[x].cnt = t[rs(x)].cnt;
}
}
void upd(int p,int l,int r,int k1,int k2,int k3,int k4)
{
t[p].sum += (1ll * t[p].cnt * k1 + 1ll * (r - l + 1 - t[p].cnt) * k3);
t[p].maxb = max(t[p].maxb , t[p].maxa + k2);
t[p].add_b = max(t[p].add_b , t[p].add_a + k2);
t[p].add_b1 = max(t[p].add_b1 , t[p].add_a1 + k4);
t[p].maxa += k1 , t[p].add_a += k1;
t[p].add_a1 += k3;
if(t[p].se != -Inf) t[p].se += k3;
}
void push_down(int p,int l,int r)
{
if(t[p].add_a == 0 && t[p].add_a1 == 0 && t[p].add_b == 0 && t[p].add_b1 == 0) return;
int maxa = max(t[ls(p)].maxa , t[rs(p)].maxa) , mid = (l + r) >> 1;
if(t[ls(p)].maxa == maxa) upd(ls(p) , l , mid , t[p].add_a , t[p].add_b , t[p].add_a1 , t[p].add_b1);
else upd(ls(p) , l , mid , t[p].add_a1 , t[p].add_b1 , t[p].add_a1 , t[p].add_b1);
if(t[rs(p)].maxa == maxa) upd(rs(p) , mid + 1 , r , t[p].add_a , t[p].add_b , t[p].add_a1 , t[p].add_b1);
else upd(rs(p) , mid + 1 , r , t[p].add_a1 , t[p].add_b1 , t[p].add_a1 , t[p].add_b1);
t[p].add_a = t[p].add_b = t[p].add_a1 = t[p].add_b1 = 0;
}
void build(int p,int l,int r)
{
t[p].add_a = t[p].add_b = t[p].add_a1 = t[p].add_b1 = 0;
if(l == r)
{
t[p].maxa = t[p].maxb = t[p].sum = a[l] , t[p].se = -Inf , t[p].cnt = 1;
return;
}
int mid = (l + r) >> 1;
build(ls(p) , l , mid);
build(rs(p) , mid + 1 , r);
push_up(p);
}
void Add(int p,int l,int r,int nl,int nr,int w)
{
if(nl <= l && nr >= r)
{
upd(p , l , r , w , w , w , w);
return;
}
push_down(p , l , r);
int mid = (l + r) >> 1;
if(nl <= mid) Add(ls(p) , l , mid , nl , nr , w);
if(nr > mid) Add(rs(p) , mid + 1 , r , nl , nr , w);
push_up(p);
}
void updmin(int p,int l,int r,int nl,int nr,int w)
{
if(w >= t[p].maxa) return;
if(nl <= l && nr >= r && w >= t[p].se)
{
upd(p , l , r , w - t[p].maxa , w - t[p].maxa , 0 , 0);
return;
}
push_down(p , l , r);
int mid = (l + r) >> 1;
if(nl <= mid) updmin(ls(p) , l , mid , nl , nr , w);
if(nr > mid) updmin(rs(p) , mid + 1 , r , nl , nr , w);
push_up(p);
}
long long query(int p,int l,int r,int nl,int nr)
{
//printf("!!!%d %d %d\n",p,l,r);
if(nl <= l && nr >= r) return t[p].sum;
push_down(p , l , r);
int mid = (l + r) >> 1;long long res = 0;
if(nl <= mid) res += query(ls(p) , l , mid , nl , nr);
if(nr > mid) res += query(rs(p) , mid + 1 , r , nl , nr);
return res;
}
int qmaxa(int p,int l,int r,int nl,int nr)
{
if(nl <= l && nr >= r) return t[p].maxa;
push_down(p , l , r);
int mid = (l + r) >> 1 , res = -Inf;
if(nl <= mid) res = max(res , qmaxa(ls(p) , l , mid , nl , nr));
if(nr > mid) res = max(res , qmaxa(rs(p) , mid + 1 , r , nl , nr));
return res;
}
int qmaxb(int p,int l,int r,int nl,int nr)
{
if(nl <= l && nr >= r) return t[p].maxb;
push_down(p , l , r);
int mid = (l + r) >> 1 , res = -Inf;
if(nl <= mid) res = max(res , qmaxb(ls(p) , l , mid , nl , nr));
if(nr > mid) res = max(res , qmaxb(rs(p) , mid + 1 , r , nl , nr));
return res;
}
int main()
{
n = read() , m = read();
for(int i = 1 ; i <= n ; i ++) a[i] = read();
build(1 , 1 , n);
//puts("YES");
for(int i = 1 ; i <= m ; i ++)
{
int opt;opt = read();
int l,r,k;l = read() , r = read();
if(opt == 1){k = read();Add(1 , 1 , n , l , r , k);}
else if(opt == 2){k = read();updmin(1 , 1 , n , l , r , k);}
else if(opt == 3){write(query(1 , 1 , n , l , r));puts("");}
else if(opt == 4){write(qmaxa(1 , 1 , n , l , r));puts("");}
else{write(qmaxb(1 , 1 , n , l , r));puts("");}
}
return 0;
}