SDOI2012 体育课
题意:
题目传送门
题解：
我们考虑一个比较暴力的分块做法，对于每一个块，我们记录\(Add[i]\)表示第\(i\)这个块的加法标记，并且记录\(Del[x]\)为\(x\)这个位置的偏移量，最后\(x\)位置的真实值就是\(a[x] + Add[x] * x - Del[x]\)。然后我们记录\(pos[i]\)为\(i\)这个块中，\(a\)最大的值的位置。 那么对于每一个\(1\)操作，答案就是\([L, R]\)这个区间中\(a\)的最大值减去\(a[1]\)，对于每个\(2\)操作，我们把块内的标记下放之后交换即可，对于每一个\(3\)操作，我们边角暴力操作，中间块打标记。剩下的唯一问题就是如何维护\(pos[x]\)的值。这里我们发现一个事情，就是由于\(t\)非负，那么一次\(3\)操作，\(pos[x]\)的位置只可能会向后移，如果我们每当\(pos[x]\)改变时暴力修改，那么一个块\(pos\)值最多的修改次数为\(\sqrt n\)次，总的修改次数是\(O(n\sqrt n)\)次。如果再考虑到\(2\)操作，总的修改次数也仍然为\(O(n\sqrt n)\)级别。所以我们对于每一个块维护一个单调栈，每次修改\(pos[x]\)的时候就暴力向后跳即可。
Code：
#pragma GCC optimize (2,"inline","Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
const int Sq = 350;
typedef long long ll;
int n, m, B;
int bl[N], que[500][Sq], pos[500], top[500];
ll Add[500], Del[500], a[N];
namespace Block {
#define Top(x) que[x][top[x]]
#define Ltop(x) que[x][top[x] - 1]
#define Mx(x) que[x][pos[x]]
void Push(int x) {
int L = (x - 1) * B + 1, R = x * B;
for(int i = L; i <= R; i++) a[i] += Add[x] * i - Del[x];
Add[x] = Del[x] = pos[x] = top[x] = 0;
}
void Build(int x) {
top[x] = 0;
int L = (x - 1) * B + 1, R = x * B;
for(int i = L; i <= R; i++) {
while(top[x] > 1 && (a[i] - a[Top(x)]) * (Top(x) - Ltop(x)) >= (a[Top(x)] - a[Ltop(x)]) * (i - Top(x))) --top[x];
que[x][++top[x]] = i;
}
for(pos[x] = 1; pos[x] <= top[x] && a[que[x][pos[x]]] <= a[que[x][pos[x] + 1]]; pos[x]++);
}
void Update(int x) {
for(;pos[x] <= top[x] && a[que[x][pos[x]]] + Add[x] * que[x][pos[x]] <= a[que[x][pos[x] + 1]] + Add[x] * que[x][pos[x] + 1]; pos[x]++);
}
void Rebuild(int x) { Push(x); Build(x); }
void Init() {
B = sqrt(n) * 2 / 3;
if(!B) B = 1;
for(int i = 1; i <= n; i++) bl[i] = (i - 1) / B + 1;
for(int i = 1; i <= bl[n]; i++) Build(i);
}
void Modify(int l, int r, int t) {
int LB = bl[l], RB = bl[r];
for(int i = l; i <= min(r, LB * B); i++) a[i] += (ll)(i - l + 1) * t;
Rebuild(LB);
if(LB != RB) {
for(int i = (RB - 1) * B + 1; i <= r; i++) a[i] += (ll)(i - l + 1) * t;
Rebuild(RB);
}
for(int i = LB + 1; i < RB; i++) {
Add[i] += t; Del[i] += (ll)(l - 1) * t; Update(i);
}
return ;
}
ll Query(int l, int r) {
int LB = bl[l], RB = bl[r];
ll ans = a[1] + Add[1] - Del[1], tmp = ans;
for(int i = l; i <= min(r, LB * B); i++) ans = max(ans, a[i] + Add[bl[i]] * i - Del[bl[i]]);
for(int i = LB + 1; i < RB; i++) ans = max(ans, a[Mx(i)] + Add[i] * Mx(i) - Del[i]);
if(LB != RB) for(int i = (RB - 1) * B + 1; i <= r; i++) ans = max(ans, a[i] + Add[bl[i]] * i - Del[bl[i]]);
return ans - tmp;
}
void Swap(int l, int r) {
int LB = bl[l], RB = bl[r];
Push(LB); if(LB != RB) Push(RB);
swap(a[l], a[r]);
Build(LB); if(LB != RB) Build(RB);
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
Block::Init();
for(int i = 1, tp, l, r; i <= m; i++) {
scanf("%d%d%d", &tp, &l, &r);
if(l > r) swap(l, r);
if(tp == 1) {
ll res = Block::Query(l, r);
printf("%lld\n", res);
}
else if(tp == 2) Block::Swap(l, r);
else {
int t;
scanf("%d", &t);
Block::Modify(l, r, t);
}
}
}
转载于:https://www.cnblogs.com/Apocrypha/p/10639027.html
相关资源：JAVA上百实例源码以及开源项目
