恋爱乃混沌之奴隶也

FutaRimeWoawaSete · 2023-01-13 15:24:59 · 个人记录

如果你觉得这道题简单，那你就自己去写一发，而不是在这里嘎嘎乱喷。

我知道很多人都会一只 \log 的做法啊，这么猛。

我们考虑使用 TB5 分治，则执行主数据结构的时间复杂度为 O(n \log n)。

瓶颈在于等价类的通用方法维护部分，我们将“范围修改问题”转化为“范围修改，单点查询”，实现时我们只需要将一个等价类的一个点抽出来做范围修改，利用 hash 合并值相同的（即同一个区间的等价类），每一层摊一只 O(|N| \log |N|) 的代价，即可在 O(n \log n + m \log m \log \log m) 的时间复杂度解决此题。

跑的很快啊，也就 1.44s，不知道吊打多少线段树做法了！！！！！！

其实只是 TB5 分治的第一份实现，因为我不清楚 TB5x 我能不能写，以及 CTS 的那道我不懂怎么对通用方法 \log n 所以就所以来写这道题了！

/*
我们每次合并出来只使用一个节点来象征，然后做二维数点就好了。 
*/
#include "bits/stdc++.h"
using namespace std;
#define ull unsigned long long
#define ll long long
const int Len = 1e5 + 5;
int n,m;ll a[Len];
ll Print[Len];
struct opt
{
    int op,l,r;ll w;
    opt(){op = l = r = w = 0;}
    opt(int OP,int L,int R,ll W){op = OP , l = L , r = R , w = W;}
}ot[Len];
mt19937 rnd(time(0));
uniform_int_distribution<ull> ab1;
inline ll read() {
    char ch = getchar();
    ll x = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void write(ll x) {
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
struct mode
{
    int x,y,z;
    mode(){x = y = z = 0;}
    mode(int X,int Y,int Z){x = X , y = Y , z = Z;}
};
struct Seg1
{
    int p[Len],pm[Len],N;ull tag[Len << 2],cs[Len];
    #define ls(p) (p << 1)
    #define rs(p) (p << 1 | 1)
    void build(int p,int l,int r)
    {
        tag[p] = 0;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(ls(p) , l , mid) , build(rs(p) , mid + 1 , r);
    }
    inline void cg(int p,ull w){tag[p] += w;return;}
    inline void push_down(int p){if(tag[p]){cg(ls(p) , tag[p]) , cg(rs(p) , tag[p]) , tag[p] = 0;}}
    void update(int pp,int l,int r,int nl,int nr,ull w)
    {
        if(nr < p[l] || nl > p[r]) return;
        if(nl <= p[l] && nr >= p[r]){cg(pp , w);return;}
        int mid = (l + r) >> 1;
        if(nl <= p[mid]) update(ls(pp) , l , mid , nl , nr , w);
        if(nr > p[mid]) update(rs(pp) , mid + 1 , r , nl , nr , w);
    }   
    void PT(int p,int l,int r)
    {
        if(l == r)
        {
            cs[l] = tag[p];
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        PT(ls(p) , l , mid) , PT(rs(p) , mid + 1 , r);
    }
}S1;
struct Nodes
{
    ll sm,tg;
    int len;
    Nodes(){sm = tg = len = 0;}
    Nodes(ll SM,ll TG,int LEN){sm = SM , tg = TG , len = LEN;}
}t[Len << 2];
inline void pushup(int x,int y){t[x].sm += t[y].sm , t[x].len += t[y].len;}//y -> x
inline void pushdown(int x,int y){t[y].sm += t[y].len * t[x].tg , t[y].tg += t[x].tg;}
inline void clr(int x){t[x] = Nodes(0 , 0 , 0);}
struct Seg2
{
    mode stk[Len << 2];int top,x,y,N;
    inline void link(int x,int y)//y -> x
    {
        stk[++ top] = mode(x , y , 0);
        pushup(x , y);
    }
    inline void back(int id)
    {
        x = stk[id].x , y = stk[id].y;
        pushdown(x , y);
    }
}S2;
inline void Work(int l,int r)
{
    const int N = S1.N;S1.build(1 , 1 , N);
    for(int i = l ; i <= r ; i ++) S1.update(1 , 1 , N , ot[i].l , ot[i].r , ab1(rnd)); 
    S1.PT(1 , 1 , N);int ct = 0;
    for(int l = 1 , r = 0 ; l <= N ; l = r + 1)
    {
        r = l;
        while(r + 1 <= N && S1.cs[l] == S1.cs[r + 1]) r ++;
        if(r - l + 1 > 1) 
        {
            ++ S2.N;
            for(int j = l ; j <= r ; j ++) S2.link(S2.N , S1.pm[j]);
        } 
        ct ++;
        S1.p[ct] = S1.p[l];
        S1.pm[ct] = (r - l + 1 > 1) ? S2.N : S1.pm[l];
        l = r;
    } 
    S1.N = ct;
}
void FD(int l,int r)
{
    vector<int> vc,vv;vc.reserve(S1.N) , vv.reserve(S1.N);
    for(int i = 1 ; i <= S1.N ; i ++) vc.push_back(S1.p[i]) , vv.push_back(S1.pm[i]);
    if(l == r) 
    {
        for(int i = 1 ; i <= S1.N ; i ++) 
        {
            if(ot[l].l <= S1.p[i] && S1.p[i] <= ot[l].r)
            {
                int x = S1.pm[i];
                if(ot[l].op == 1){t[x].sm += t[x].len * ot[l].w;t[x].tg += ot[l].w;}
                else{Print[l] = t[x].sm;}
                break;
            }
        }
        return;
    }
    int mid = (l + r) >> 1 , tp2 = S2.top;
    Work(l , mid);FD(l , mid);
    int lst = 0;
    while(S2.top > tp2) 
    {
        if(S2.stk[S2.top].x != lst)
        {
            if(lst) clr(lst) , S2.N --;
            lst = S2.stk[S2.top].x;
        }
        S2.back(S2.top --);
    }
    if(lst) clr(lst) , S2.N --;
    S1.N = 0;
    for(int j = 0 ; j < (int)vc.size() ; j ++){++ S1.N;S1.p[S1.N] = vc[j] , S1.pm[S1.N] = vv[j];}
    Work(mid + 1 , r);FD(mid + 1 , r);
    lst = 0;
    while(S2.top > tp2) 
    {
        if(S2.stk[S2.top].x != lst)
        {
            if(lst) clr(lst) , S2.N --;;
            lst = S2.stk[S2.top].x;
        }
        S2.back(S2.top --);
    }
    if(lst) clr(lst) , S2.N --;S1.N = 0;
    for(int j = 0 ; j < (int)vc.size() ; j ++){++ S1.N;S1.p[S1.N] = vc[j] , S1.pm[S1.N] = vv[j];}
}
int main()
{
    n = read() , m = read();
    for(int i = 1 ; i <= n ; i ++) 
    {
        a[i] = read();
        t[++ S2.N] = Nodes(a[i] , 0 , 1);
    }
    for(int i = 1 ; i <= m ; i ++)
    {
        int op,l,r;ll k;op = read() , l = read() , r = read();
        if(op == 1) k = read();
        ot[i] = opt(op , l , r , k);
    }
    for(int i = 1 ; i <= n ; i ++){++ S1.N;S1.p[i] = S1.pm[i] = i;}
    Work(1 , m);
    FD(1 , m);
    for(int i = 1 ; i <= m ; i ++) if(ot[i].op == 2) printf("%lld\n",Print[i]);
    return 0;
}