2019 ICPC 南昌网络赛I:Yukino With Subinterval(CDQ分治)

Yukino With Subinterval

Yukino has an array a_1, a_2 \cdots a_na1,a2⋯a**n. As a tsundere girl, Yukino is fond of studying subinterval.

Today, she gives you four integers l, r, x, yl,r,x,y, and she is looking for how many different subintervals [L, R][L,R] are in the interval [l, r][l,r] that meet the following restraints:

a_L =a_{L+1} =\cdots=a_Ra**L=a**L+1=⋯=a**R, and for any i \in [L,R], x \le a_i \le yi∈[L,R],x≤a**i≤y.
The length of such a subinterval should be maximum under the first restraint.

Note that two subintervals [L_1,R_1] , [L_2,R_2][L1,R1],[L2,R2]are different if and only if at least one of the following formulas is true:

L1 \cancel= L2L1=L2
R1 \cancel= R2R1=R2

Yukino, at the same time, likes making tricks. She will choose two integers pos,vpos,v, and she will change a_{pos}apo**s to vv.

Now, you need to handle the following types of queries:

11 pos \ vpos v: change a_{pos}apo**s to vv
22 l \ r \ x \ yl r x y: print the number of legal subintervals in the interval [l, r][l,r]

Input

The first line of the input contains two integers n, m (1 \le n, m \le 2 \times 10^5)n,m(1≤n,m≤2×105) – the numbers of the array and the numbers of queries respectively.

The second line of the input contains nn integers a_i (1 \le a_i \le n)a**i(1≤a**i≤n).

For the next mm line, each containing a query in one of the following queries:

11 pospos vv (1 \le pos, v \le n)(1≤pos,v≤n): change a_{pos}apo**s to vv
22 l \ r \ x \ yl r x y (1 \le l \le r \le n) (1 \le x \le y \le n)(1≤l≤r≤n)(1≤x≤y≤n): print the number of legal subintervals in the interval [l,r][l,r]

Output

For each query of the second type, you should output the number of legal subintervals in the interval [l, r][l,r].

样例输入复制

6 3

3 3 1 5 6 5

2 2 3 4 5

1 3 2

2 1 6 1 5

样例输出复制

0

4

样例解释

For the first operations, there are 33 different subintervals ([2, 2],[3, 3],[2,3])([2,2],[3,3],[2,3]) in the interval [2, 3][2,3], but none of them meets all the restraints.

For the third operations, the legal subintervals in interval [1, 6][1,6] are: [1, 2], [3, 3], [4, 4], [6, 6][1,2],[3,3],[4,4],[6,6]

Notes that although subintervals [1,1][1,1] and [2,2][2,2] also meet the first restraint, we can extend them to subinterval [1, 2][1,2]. So the length of them is not long enough, which against the second one.

题目链接：https://nanti.jisuanke.com/t/41356

题意：

给你一个含有n个数的数组，和m个操作

操作1：

将a[pos] 变为val

操作2：

询问在$[l,r]$ 中有多少个子区间满足数值在$[x,y] $ 之间，每一个子区间是长度尽可能大的相同数字。

思路：

将数组中 $a[i] $ ，转为在二维坐标平面上的点$(i,a[i])$ ,

那么就转为了一个带修改的二维平面中询问矩阵内点权值和的问题。

这是一个经典的三维偏序问题。

可以用CDQ分治来解决。

不会的话可以先学习一下这题：

https://www.cnblogs.com/qieqiemin/p/11613573.html

本题还需要注意几点：

因为连续相同的数值只贡献一个，所以我们把连续相同的只把第一个点放入平面中（即放入cdq的离线操作中）

那么对于每一个询问，我们就要特判一下$(l,a[l])$ 这个点，如果$a[l]$ 在 $[x,y]$ 之间，并且满足

$l >1 $

$a[l]==a[l-1] $

这2个条件，都需要对这个询问的答案加上1。即加上a[l]为开头的子区间的贡献，

以及修改操作，需要判断改变$a[i]$ 对$a[i-1]，a[i+1]$ 的影响，以及如果更改前的$a[i]$ 是一个子区间的开头，需要去掉原来的影响（加上相反的值即可。）

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define sz(a) int(a.size())

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))

#define du2(a,b) scanf("%d %d",&(a),&(b))

#define du1(a) scanf("%d",&(a));

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}

void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline void getInt(int *p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll tree[maxn];

int lowbit(int x)

{

    return -x & x;

}

ll ask(int x)

{

//    cout<<x<<" ";

    ll res = 0ll;

    while (x) {

        res += tree[x];

        x -= lowbit(x);

    }

//    cout<<res<<endl;

    return res;

}

void add(int x, ll val)

{

//    cout<<x<<" "<<val<<endl;

    while (x < maxn) {

        tree[x] += val;

        x += lowbit(x);

    }

}

int n, m;

struct node {

    int time;

    int op;

    int x, y;

    int val;

    int ansid;

    node() {}

    node(int tt, int oo, int xx, int yy, int vv, int aa)

    {

        time = tt;

        op = oo;

        x = xx;

        y = yy;

        val = vv;

        ansid = aa;

    }

    bool operator < (const node &bb) const

    {

        if (time != bb.time) {

            return time < bb.time;

        } else if (x != bb.x) {

            return x < bb.x;

        } else if (y != bb.y) {

            return y < bb.y;

        } else {

            return op < bb.op;

        }

    }

    bool operator<= (const node &bb )const

    {

        if (x != bb.x) {

            return x < bb.x;

        } else if (y != bb.y) {

            return y < bb.y;

        } else {

            return op < bb.op;

        }

    }

} a[maxn], b[maxn];

int ans[maxn];

int tot;

int anstot;

int c[maxn];

int sym[maxn];

void cdq(int l, int r)

{

    if (l == r) {

        return ;

    }

    int mid = (l + r) >> 1;

    cdq(l, mid);

    cdq(mid + 1, r);

    int ql = l;

    int qr = mid + 1;

    repd(i, l, r) {

        if (qr > r || (ql <= mid && a[ql] <= a[qr])) {

            if (a[ql].op == 1) {

                add(a[ql].y, a[ql].val);

                sym[i] = 1;

            }

            b[i] = a[ql++];

        } else {

            if (a[qr].op == 2) {

                ans[a[qr].ansid] += a[qr].val * ask(a[qr].y);

            }

            b[i] = a[qr++];

        }

    }

    ql = l;

    qr = mid + 1;

    repd(i, l, r) {if (qr > r || (ql <= mid && a[ql] <= a[qr])) {if (a[ql].op == 1) {add(a[ql].y, -a[ql].val);} ql++;} else {qr++;}}

    repd(i, l, r) {a[i] = b[i];}

}

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    du2(n, m);

    repd(i, 1, n) {

        du1(c[i]);

        if (c[i] != c[i - 1]) {

            a[++tot] = node(-1, 1, i, c[i], 1, 0);

        }

    }

    // node(int tt, int oo, int xx, int yy, int vv, int aa)

    repd(i, 1, m) {

        int op;

        du1(op);

        if (op == 1) {

            int pos, v;

            du2(pos, v);

            if (pos != n && c[pos] == c[pos + 1]) {

                a[++tot] = node(i, 1, pos + 1, c[pos + 1], 1, 0);

            }

            if (pos == 1 || c[pos] != c[pos - 1]) {

                a[++tot] = node(i, 1, pos, c[pos], -1, 0);

            }

            c[pos] = v;

            if (pos != n && c[pos] == c[pos + 1]) {

                a[++tot] = node(i, 1, pos + 1, c[pos + 1], -1, 0);

            }

            if (pos == 1 || c[pos] != c[pos - 1]) {

                a[++tot] = node(i, 1, pos, c[pos], 1, 0);

            }

        } else {

            int l, r, x, y;

            du2(l, r);

            du2(x, y);

            if (l != 1 && c[l] == c[l - 1] && c[l] <= y && c[l] >= x) {

                ans[anstot]++;

            }

            a[++tot] = node(i, 2, r, y, 1, anstot);

            a[++tot] = node(i, 2, l - 1, x - 1, 1, anstot);

            a[++tot] = node(i, 2, r, x - 1, -1, anstot);

            a[++tot] = node(i, 2, l - 1, y, -1, anstot++);

        }

    }

    sort(a + 1, a + 1 + tot);

    cdq(1, tot);

    repd(i, 0, anstot - 1) {

        printf("%d\n", max(ans[i], 0));

    }

    return 0;

}

inline void getInt(int *p)

{

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    } else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西