欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3246 [HNOI2016]序列(离线 差分 树状数组)

程序员文章站 2022-03-18 15:42:33
题意 "题目链接" Sol 好像搞出了一个和题解不一样的做法(然而我考场上没写出来还是爆零0) 一个很显然的思路是考虑每个最小值的贡献。 预处理出每个数左边第一个比他小的数,右边第一个比他大的数。 那么$[L_i + 1, i]$对$[i, R_i]$中的每个数都会有$a[i]$的贡献。 我们可以抽 ......

题意

题目链接

sol

好像搞出了一个和题解不一样的做法(然而我考场上没写出来还是爆零0)

一个很显然的思路是考虑每个最小值的贡献。

预处理出每个数左边第一个比他小的数,右边第一个比他大的数。

那么\([l_i + 1, i]\)\([i, r_i]\)中的每个数都会有\(a[i]\)的贡献。

我们可以抽象成一个二维平面内的矩形加。

询问就是询问最下角为\((l, l)\),右上角为\((r, r)\)的矩形内的权值

也就是我们需要解决这么一个问题:两个操作, 矩形加矩形求和,而且前者都在后者的前面执行

我们可以把所有矩形加操作全都向右上角差分,所有询问操作全都向左下角差分。这样我们就只需要考虑每个\((i, j)\)左下角的所有修改\((x, y)\)的影响,这部分的权值为\((i - x + 1) * (j - y + 1) * w\)

直接拆开,发现可以用树状数组维护(单点修改,查前缀和)。然后就做完了

复杂度\(o(nlogn)\)

/*
*/
#include<bits/stdc++.h>
#define ll long long 
#define fi first
#define se second
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++)
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
char obuf[1<<24], *o = obuf;
void print(int x) {if(x > 9) print(x / 10); *o++ = x % 10 + '0';}
#define os  *o++ = '\n';
#define fout fwrite(obuf, o-obuf, 1 , stdout); 
using namespace std;
const int maxn = 1e5 + 10, inf = 1e9 + 10;
template<typename a, typename b> inline bool chmax(a &x, b y) {return x < y ? x = y, 1 : 0;}
template<typename a, typename b> inline bool chmin(a &x, b y) {return x > y ? x = y, 1 : 0;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, q, a[maxn],  st[maxn], l[maxn], r[maxn]; 
ll ans[maxn];
struct modify {
    int h;ll v;
};
vector<modify> tag[maxn];
struct query {
    int h, id, opt;
};
vector<query> q[maxn];
void add(int x1, int y1, int x2, int y2, int v) {
    tag[x1].push_back({y1, v});
    tag[x2 + 1].push_back({y1, -v});
    tag[x1].push_back({y2 + 1, -v});
    tag[x2 + 1].push_back({y2 + 1, v});
}
void query(int x1, int y1, int x2, int y2, int id) {
    q[x2].push_back({y2, id, 1});
    q[x1 - 1].push_back({y2, id, -1});
    q[x2].push_back({y1 - 1, id, -1});
    q[x1 - 1].push_back({y1 - 1, id, 1});
}
#define lb(x) (x & (-x))
ll s1[maxn], s2[maxn], s3[maxn], s4[maxn];
void treeadd(int x, ll v1, ll v2, ll v3, ll v4) {
    while(x <= m) 
        s1[x] += v1, s2[x] += v2, s3[x] += v3, s4[x] += v4, x += lb(x);
}
pair<pair<ll, ll>, pair<ll, ll> > treequery(int x) {
    pair<pair<ll, ll>, pair<ll, ll> > ans;
    while(x) 
        ans.fi.fi += s1[x], ans.fi.se += s2[x], ans.se.fi += s3[x], ans.se.se += s4[x], x -= lb(x);
    return ans;
}
#undef lb
void solve() {
    for(int i = 1; i <= m; i++) {   
        for(auto y: tag[i]) {
            int v = y.v;
            treeadd(y.h, 1ll * v, 1ll * (y.h - 1) * v, 1ll * (i - 1) * v, 1ll * (y.h - 1) * (i - 1) * v);
        }
        for(auto x : q[i]) {
            ll sumv = 0, sumyv = 0, sumxv = 0, sumxyv = 0;
            pair<pair<ll, ll>, pair<ll, ll> > tmp = treequery(x.h);
            sumv = tmp.fi.fi;
            sumyv = tmp.fi.se;
            sumxv = tmp.se.fi;
            sumxyv = tmp.se.se;
            int j = x.h;
            ans[x.id] += 1ll * x.opt * (1ll * i * j * sumv - 1ll * i * sumyv - 1ll * j * sumxv + sumxyv);
        }
    }
}

void pre() {
    a[0] = -inf; a[n + 1] = -inf; int top = 0;
    for(int i = 1; i <= n + 1; i++) {
        while(top && a[i] < a[st[top]]) r[st[top--]] = i;
        l[i] = st[top];
        st[++top] = i;
    }
    for(int i = 1; i <= n; i++)
        if((i <= r[i] - 1) && (l[i] + 1 <= i)) 
            add(i, l[i] + 1, r[i] - 1, i, a[i]);
}
signed main() {
    //freopen("a.in", "r", stdin); freopen("b.out", "w", stdout);
    n = read(); m = n + 1; q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    pre();
    for(int i = 1; i <= q; i++) {
        int l = read(), r = read(), ans = 0;
        query(l, l, r, r, i);
    }
    solve();
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}