恋爱乃混沌之奴隶也
FutaRimeWoawaSete
2023-01-13 15:24:59
如果你觉得[这道题](https://www.luogu.com.cn/problem/P3372)简单，那你就自己去写一发，而不是在这里嘎嘎乱喷。
我知道很多人都会一只 $\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$ 所以就所以来写这道题了！
```cpp
/*
我们每次合并出来只使用一个节点来象征，然后做二维数点就好了。
*/
#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;
}
```