题解：CF1824D LuoTianyi and the Function

· · 题解

CF1824D LuoTianyi and the Function

分析

拆式子

式子都给我们了，上手考虑拆贡献。

因为 g(i,j) 是独立的，有：

\sum\limits_{i=l}^r\sum\limits_{j=x}^y g(i,j) = \sum\limits_{i=l}^r\sum\limits_{j=1}^y g(i,j) - \sum\limits_{i=l}^r\sum\limits_{j=1}^{x-1} g(i,j)

题目中说：当 i > j 时，g(i,j) = 0。

所以有：

\begin{aligned} \sum\limits_{i=l}^r\sum\limits_{j=x}^y g(i,j) &= \sum\limits_{i=l}^r\sum\limits_{j=1}^y g(i,j) - \sum\limits_{i=l}^r\sum\limits_{j=1}^{x-1} g(i,j) \\ &= \sum\limits_{i=l}^{\min(r,y)}\sum\limits_{j=1}^y g(i,j) - \sum\limits_{i=l}^{\min(r,x - 1)}\sum\limits_{j=1}^{x-1} g(i,j)\\ &= \sum\limits_{j=1}^y\sum\limits_{i=l}^{\min(r,y)} g(i,j) - \sum\limits_{j=1}^{x-1}\sum\limits_{i=l}^{\min(r,x - 1)} g(i,j) \end{aligned}

对于外面这一维求和（即 \sum\limits_{j = 1}），我们可以扫描线去做。

里面这一维求和（即 \sum\limits_{i = l}^{r^{\prime}}），我们可以做一个历史和，也就是计算当 i:l\sim r^{\prime} 时，g(i,j) 对于 j:1\sim k 产生的 k 个版本的贡献的总和。

我们可以把询问离线下来，将询问拆开，分别插入到区间的右端点上，在遍历的时候计算答案。

因为我们做的是前缀和差分，插入的时候记得记录贡献的符号！

贡献的计算

为了直观的体会贡献是如何变化的，可以手模一些例子：

如图：

这是当 j = 8 时的 g(i,j) 数组。

考虑 j = 9 时的情况：

  1. 当 a_9 = 6 时，如图： 此时上一个 6 所在的颜色段和其下一个颜色段合并了，并且贡献变为其下一个颜色段的 g(i,j)，在末尾新增了一个 g(i,j) = 9 的新颜色段。

  2. 当 a_9 = 4 时，如图： 由于先前没有 a_i = 4，所以只在末尾新增了一个 g(i,j) = 4 的新颜色段。

所以，我们可以用set维护这些颜色段，在扫描的时候判断是否需要合并两个颜色段，并不断在末尾新增颜色段。

当两个颜色段合并时，用历史和线段树做区间覆盖操作。

在所有操作结束之后，更新历史和。

最后将答案输出即可。

常数问题

我喜欢通过构造矩阵来计算历史和。

但这道题卡常。

显然，类似于 [NOIP2022] 比赛，我们需要将矩阵拆开。

我们一共有两种矩阵：

  1. 覆盖矩阵
1 & 0 & 0 \\ 0 & 0 & d \\ 0 & 0 & 1 \\ \end{bmatrix}
  1. 更新矩阵
1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}

随机累乘矩阵，可以发现我们实际需要维护的位置只有 (a,b,c,d) 这四个位置：

1 & a & b \\ 0 & c & d \\ 0 & 0 & 1 \\ \end{bmatrix}

那么手模矩阵乘法就可以将 3^3 的常数减小到 3\sim 4 左右。

AC-code：

我的代码常数比较大，所以用快读和C++20 64bits winlibs选项才能过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace IO {
    inline char gc() {
        static const int IN_LEN = 1 << 18 | 1;
        static char buf[IN_LEN], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
    }
    template <typename T>
    inline void read(T &x) {
        static char ch, ff;
        ch = gc(), ff = 0;
        for(; !isdigit(ch); ch = gc())
            ff |= ch == '-';
        for(x = 0; isdigit(ch); ch = gc())
            x = (x << 3) + (x << 1) + (ch ^ 48);
        ff && (x = -x);
        return;
    }
    template <typename T, typename ...t>
    void read(T&x, t& ...y) {
        read(x), read(y...);
        return;
    }
    template <typename T>
    inline void print(T x) {
        static int pr, pri[105], temp;
        pr = 0, temp = x;
        if(x < 0)
            fputc('-', stdout), x = -x;
        if(!x) {
            fputc(48, stdout);
            return;
        }
        while(x)
            pri[++pr] = x % 10, x /= 10;
        for(; pr; pr--)
            fputc(pri[pr] + 48, stdout);
        x = temp;
        return;
    }
    template <typename T, typename ...t>
    void print(T&x, t& ...y) {
        print(x), fputc(' ', stdout), print(y...);
        return;
    }
}
using namespace IO;

struct tag{
    int x[7];
    inline void init() {
        x[1] = x[4] = x[6] = 1;
        x[2] = x[3] = x[5] = 0;
    }
    inline int& operator [](const int pos) {return x[pos];}
    inline friend tag operator * (tag& A,tag& B) {
        tag c;c.init();
        c[2] = A[2] * B[4] + B[2];
        c[3] = B[3] + A[2] * B[5] + A[3];
        c[4] = A[4] * B[4];
        c[5] = B[5] * A[4] + A[5];
        return c;
    }
    inline friend bool operator != (tag A,tag B) {
        for(int i = 0;i<7;i++)
            if(A[i] != B[i])
                return true;
        return false;
    }
    inline void print(string s) {
        cout<<"test for "<<s<<" matrix\n";
        cout<<x[1]<<' '<<x[2]<<' '<<x[3]<<'\n';
        cout<<0<<' '<<x[4]<<' '<<x[5]<<'\n';
        cout<<0<<' '<<0<<' '<<x[6]<<'\n'; 
   }
};

inline tag addtag(int k) {tag c;c.init();c[4] = 0;c[5] = k;return c;}
inline tag updtag() {tag c;c.init();c[2] = 1;return c;}
inline tag NONE(){tag c;c.init();return c;}

struct vet{
    int y[4];
    void init() {y[1] = y[2] = y[3] = 0;}
    int& operator [](const int pos) {return y[pos];}
    inline friend vet operator + (vet a,vet b) {
        vet c;c.init();
        c[1] = a[1] + b[1];
        c[2] = a[2] + b[2];
        c[3] = a[3] + b[3];
        return c;
    }
    inline void print(string s) {
        cout<<'\n';
        cout<<"test for "<<s<<" vector\n";
        cout<<y[1]<<'\n';
        cout<<y[2]<<'\n';
        cout<<y[3]<<'\n';
        cout<<'\n';
    }
};

inline vet operator * (tag A,vet B) {
    vet c;c.init();
    c[1] = B[1] + B[2] * A[2] +B[3] * A[3];
    c[2] = B[2] * A[4] + A[5] * B[3];
    c[3] = B[3];
    return c;
}

const int N = 1e6+5;
int n,q,a[N],ans[N],pre[N];
vector<array<int,4>> R[N];
set<int> s;

#define ls (p << 1)
#define rs (ls | 1)
#define mid ((pl + pr) >> 1)
tag T[N<<2];vet V[N<<2];
bool ext[N<<2];

inline void push_up(int p) {
    V[p] = V[ls] + V[rs];
}

inline void addtag(int p,tag x){
    V[p] = x * V[p];
    T[p] = x * T[p];
    ext[p] = true;
}

inline void push_down(int p){
    if(ext[p]) {
        addtag(ls,T[p]);
        addtag(rs,T[p]);
        T[p].init();
        ext[p] = false;
    }
}

inline void build(int p,int pl,int pr) {
    T[p].init();
    V[p].init();
    if(pl == pr) {
        V[p][3] = 1;
        return;
    }
    build(ls,pl,mid);
    build(rs,mid+1,pr);
    push_up(p);
}

inline void update(int p,int pl,int pr,int l,int r,tag x) {
    if(l <= pl && pr <= r) {addtag(p,x);return;}
    push_down(p);
    if(l <= mid) update(ls,pl,mid,l,r,x);
    if(r > mid) update(rs,mid+1,pr,l,r,x);
    push_up(p);
}

inline vet query(int p,int pl,int pr,int l,int r){
    if(l <= pl && pr <= r) return V[p];
    push_down(p);
    if(r <= mid) return query(ls,pl,mid,l,r);
    else if(l > mid) return query(rs,mid+1,pr,l,r);
    else return query(ls,pl,mid,l,r) + query(rs,mid+1,pr,l,r);
}

signed main() {
    read(n,q);
    for(int i = 1;i<=n;i++) read(a[i]);
    for(int i = 1,l,r,x,y;i<=q;i++) {
        read(l,r,x,y);
        R[x - 1].emplace_back((array<int,4>){-1,l,min(r,x - 1),i});
        R[y].emplace_back((array<int,4>){1,l,min(r,y),i});
    }
    s.insert(0);
    build(1,1,n);
    for(int i = 1;i<=n;i++) {
        auto it = s.lower_bound(pre[a[i]]);
        if(it != s.begin()) {
            int l = *(--it),v;
            ++it;++it;
            v = (it == s.end()) ? i : (*it);
            if(l < pre[a[i]]) update(1,1,n,l+1,pre[a[i]],addtag(v));
        }
        update(1,1,n,i,i,addtag(i));
        if(pre[a[i]]) s.erase(pre[a[i]]);
        s.insert(i);
        pre[a[i]] = i;
        update(1,1,n,1,i,updtag());
        for(auto c:R[i]) 
            if(c[1] <= c[2]) 
                ans[c[3]] += c[0] * query(1,1,n,c[1],c[2])[1];
    }
    for(int i = 1;i<=q;i++) print(ans[i]), fputc('\n', stdout);
    return 0;
}