筹备计划
题目链接：ybtoj高效进阶 21172
题目大意
给你一个数组，然后要你支持一些操作：
给一个位置加值或者减值，询问最优的位置，让一段区间里面的位置都不能是最优位置，或让一段区间里面的位置可以是最优位置。
最优位置是可以作为最优位置的位置中，费用最小的。
定义一个位置的费用是每个位置到它的距离乘上每个位置的权值。
思路
考虑用数据结构维护。
首先化简式子：(sumlimits_{i=1}^n(a_i|x-i|))
(xsumlimits_{i=1}^x a_i-sumlimits_{i=1}^xa_i imes i-xsumlimits_{i=x+1}^na_i+sumlimits_{i=x+1}^na_i imes i)
不难看到分成四个部分，可以用四个树状数组维护。
然后至于可以不可以作为最优点，我们用线段树来搞，那至于找位置，我们也可以直接在这个线段树上二分。
就好惹。
代码
#include<cstdio>
#define ll long long
using namespace std;
int n, q, op, x, y, re, pl;
ll maxn;
char c;
int read() {
re = 0;
c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re;
}
void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
struct SZSJ {//树状数组
ll val[200001];
void insert(int x, ll va) {
if (x <= 0) return ;
for (; x <= n; x += x & (-x))
val[x] += va;
}
ll query(int x) {
ll re = 0;
for (; x; x -= x & (-x))
re += val[x];
return re;
}
}T1, T2, T3, T4;
struct XD_tree {//线段树
bool ckand[200001 << 2], ckor[200001 << 2];
short lzyck[200001 << 2];
// ll val[200001 << 2], nm[200001 << 2];
void down(int now) {
if (lzyck[now] != -1) {
ckand[now << 1] = ckand[now << 1 | 1] = lzyck[now];
ckor[now << 1] = ckor[now << 1 | 1] = lzyck[now];
lzyck[now << 1] = lzyck[now << 1 | 1] = lzyck[now];
lzyck[now] = -1;
}
}
void col(int now, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) {
ckand[now] = ckor[now] = x;
lzyck[now] = x;
return ;
}
down(now);
int mid = (l + r) >> 1;
if (L <= mid) col(now << 1, l, mid, L, R, x);
if (mid < R) col(now << 1 | 1, mid + 1, r, L, R, x);
ckand[now] = ckand[now << 1] & ckand[now << 1 | 1];
ckor[now] = ckor[now << 1] | ckor[now << 1 | 1];
}
void insert(int pl, ll va) {
T1.insert(n - (pl - 1) + 1, va * pl);
T2.insert(n - (pl - 1) + 1, -va);
T3.insert(pl + 1, -va * pl);
T4.insert(pl + 1, va);
}
ll query(int pl) {
return pl * (T2.query(n - pl + 1) + T4.query(pl)) + (T1.query(n - pl + 1) + T3.query(pl));
}
int get_l(int now, int l, int r, int L, int R) {
if (l != r) down(now);
if (L <= l && r <= R) {
if (ckand[now]) return l;
if (!ckor[now]) return -1;
int mid = (l + r) >> 1;
if (ckor[now << 1]) return get_l(now << 1, l, mid, L, R);
else return get_l(now << 1 | 1, mid + 1, r, L, R);
}
int mid = (l + r) >> 1, re = -1;
if (L <= mid) re = get_l(now << 1, l, mid, L, R);
if (re != -1) return re;
if (mid < R) re = get_l(now << 1 | 1, mid + 1, r, L, R);
return re;
}
int get_r(int now, int l, int r, int L, int R) {
if (l != r) down(now);
if (L <= l && r <= R) {
if (ckand[now]) return r;
if (!ckor[now]) return -1;
int mid = (l + r) >> 1;
if (ckor[now << 1 | 1]) return get_r(now << 1 | 1, mid + 1, r, L, R);
else return get_r(now << 1, l, mid, L, R);
}
int mid = (l + r) >> 1, re = -1;
if (mid < R) re = get_r(now << 1 | 1, mid + 1, r, L, R);
if (re != -1) return re;
if (L <= mid) re = get_r(now << 1, l, mid, L, R);
return re;
}
}T;
int main() {
// freopen("position.in", "r", stdin);
// freopen("position.out", "w", stdout);
// freopen("read.txt", "r", stdin);
// freopen("write.txt", "w", stdout);
n = read(); q = read();
for (int i = 1; i <= n; i++) {
x = read();
if (x) T.insert(i, x);
}
T.lzyck[1] = T.ckand[1] = T.ckor[1] = 1;
int l, r;
while (q--) {
op = read();
if (op == 1) {
x = read(); y = read();
T.insert(x, y);
}
if (op == 2) {
x = read(); y = read();
T.insert(x, -y);
}
if (op == 3) {
x = read(); y = read();
T.col(1, 1, n, x, y, 1);
}
if (op == 4) {
x = read(); y = read();
T.col(1, 1, n, x, y, 0);
}
l = 1, r = n;
while (r - l + 1 > 2) {
int mid = (l + r) >> 1;
if (T.query(mid) <= T.query(mid + 1)) r = mid;
else l = mid + 1;
}
maxn = 1e18; pl = -1;
for (int i = l; i <= r; i++) {
ll noww = T.query(i);
if (noww < maxn) maxn = noww, pl = i;
}
l = T.get_r(1, 1, n, 1, pl); r = T.get_l(1, 1, n, pl, n);
if (l == -1 && r == -1) {
putchar('-'); putchar('1');
}
else if (l == -1 || r == -1) {
write(l + r + 1);
}
else {
if (T.query(l) <= T.query(r)) write(l);
else write(r);
}
putchar('
');
}
return 0;
}