371ABC题解

D - 1D Country

对于每次询问
二分出对应的L村庄编号和R村庄编号
村庄编号为前缀和下标，前缀和处理区间和。

E - I Hate Sigma Problems

经典思想——拆位
由于每个元素 $x$ 对区间的贡献独立，所以可以单独考虑每种元素的贡献。
对于元素 $x$

方法一：考虑产生贡献的区间数
首先区间一定包含下标 $i, a_i = x$.
不妨从前往后枚举 $i$,那么区间左端点 $L$ 设置在 $i$ 左边(包含)，右端点 $R$ 设置在 $i$ 右边(包含)
设置 $R$ 可以任意取值，考虑 $L$ 的取值可能，使得不与前面重复。
显然 $L$ 不能小于等于前一个是 $x$ 的下标 $pre_x$,否则会与前一个位置重复计算区间，使得答案增大。
所以 $L$ > $pre_x$.
综上，包含 $位置i$ 的区间数就是 $(i - pre_x) * (n - i + 1)$
(代码异常的短)

typedef long long ll;
int n, pre[N];

void solve() {
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        ans += 1ll * (i - pre[x]) * (n - i + 1);
        pre[x] = i;
    }
    cout << ans;
}

方法二：考虑不产生贡献的区间数
不产生贡献的区间一定不包含 $x$
那么该区间一定夹在2个连续的 $x$ 之间，为方便计算，引入下标 $a_0 = x, a_{n + 1} = x$
旧问题就转换成新问题——长度为 $len$ 的区间有多少子区间？
分讨子区间长度大于1和等于1
总和就是 $C(len, 2) + len$
合法区间就是非法互补的数目

typedef long long ll;
int n;
vector<int> v[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) v[i].push_back(0);
    for (int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    for (int i = 1; i <= n; i ++ ) v[i].push_back(n + 1);
    ll ans = 0;
    for (int x = 1; x <= n; x ++ ){
        ll r0 = 0; // 非法方案
        for (int i = 0; i + 1 < v[x].size(); i ++ ){
            int l = v[x][i] + 1, r = v[x][i + 1] - 1;
            if (l > r) continue;
            ll len = r - l + 1;
            r0 += len * (len - 1) / 2 + len;
        }
        ans += 1ll * n * (n - 1) / 2 + n - r0;
    }
    cout << ans;
}

F - Takahashi in Narrow Road

难点解析：不能越位，像是在一条轨道上推积木.

Tip

经典套路
对于第 $i$ 人坐标 $x_i$, 定义 $新x_i = x_i - i$

旧 $x_i$ 单调递增使得新 $x_i$ 单调不递减,很难不让人想到 $log$ 级别的做法
给定 $(t, g)$, 分讨推动 $t$ 的方向
如果是 $x_t \leq g$ ,需要推动所有在 $[x_t, g]$ 的 $x_i$.否则需要推动所有在 $[g, x_t]$ 的$x_i$.
贪心最小，一定成距离差1的块，因下标同样差1，所以最终区间内 $x_i$ 相同且为 $g-t$,消耗的步数就是初末区间和的差值.
如何找到最终的区间左右端点呢，由于 $x_i$ 单调不递减，所以可以二分
综上，二分线段树

/*
区间修改+区间查询
维护：区间和 
操作：查询+区间赋值
*/

const int N = 2e5 + 10;
typedef long long ll;

ll n, q, x[N];

struct info{
    ll sum, sz;
    info(){sum = 0; sz = 1;}
    info(ll sum, ll sz):sum(sum), sz(sz){}
};

struct tag{
    ll d;
    tag(){d = -1;}
    tag(ll d):d(d){}
};

info operator+(const info &l, const info &r){
    return {l.sum + r.sum, l.sz + r.sz};
}

info operator+(const info &v, const tag &t){ // 区间修改
    return {v.sz * t.d, v.sz};
}

tag operator+(const tag &t1, const tag &t2){ //懒标记和并
    return {t2.d};
}

struct Node{
    tag t;
    info val;
} seg[N * 4];

void settag(int id, tag t){
    seg[id].val = seg[id].val + t;
    seg[id].t = seg[id].t + t;
}

void pushdown(int id){ // 每一步都需要标记下传
    if (seg[id].t.d != -1){ // 标记非空
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        //初始化标记
        seg[id].t.d = -1;
    }
}

void update(int id){
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}

void build(int id, int l, int r){
    if (l == r){
        seg[id].val = info(x[l], 1);
        seg[id].t = tag(-1);
    }
    else{
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        update(id);
    }
}

info query(int id, int l, int r, int ql, int qr){
    if (l == ql && r == qr){
        return seg[id].val;
    }
    int mid = (l + r) / 2;
    pushdown(id);
    if (qr <= mid)
        return query(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return query(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return query(id * 2, l, mid, ql, mid) +
               query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}

void modify(int id, int l, int r, int ql, int qr, tag t){
    if (l == ql && r == qr)
    {
        settag(id, t);
        return;
    }
    int mid = (l + r) / 2;
    pushdown(id);
    if (qr <= mid)
        modify(id * 2, l, mid, ql, qr, t);
    else if (ql > mid)
        modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else
    {
        modify(id * 2, l, mid, ql, mid, t);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> x[i], x[i] -= i;
    build(1, 1, n);
    cin >> q;
    ll ans = 0;
    while (q -- ){
        ll t, g;
        cin >> t >> g; g -= t;
        //讨论方向
        ll xt = query(1, 1, n, t, t).sum;
        if (xt <= g){ // 向右  //[xt, g]  
            int l = t, r = n;
            while (l < r){
                int mid = (l + r + 1) / 2;
                if (query(1, 1, n, mid, mid).sum <= g) l = mid;
                else r = mid - 1;
            }
            ans += g * (r - t + 1) - query(1, 1, n, t, r).sum;
            modify(1, 1, n, t, r, tag(g));
        }else{ //向左  //[g, xt]
            int l = 1, r = t;
            while (l < r){
                int mid = (l + r) / 2;
                if (query(1, 1, n, mid, mid).sum >= g) r = mid;
                else l = mid + 1;
            }
            ans += query(1, 1, n, l, t).sum - g * (t - l + 1);
            modify(1, 1, n, l, t, tag(g));
        }
    }
    cout << ans;
}