高端分块题3710
P3710。
拿到题目之后，我们可以发现：你无法通过除法操作或者减法操作来撤销一个加法操作或者乘法操作。因为他们之后可能还套了操作。
这样子不行，那么我们就暴力一点考虑。每一次遇到撤销操作就把所有操作全部重新执行一遍算答案。
但是这样子单次撤销复杂度太高了，我们可以考虑通过分块来平衡一下。
具体而言，我们对时间轴进行分块。然后对于每一个块都开一棵线段树，每一个点就表示一个值
维护完这个之后，你就可以对于查询操作整块查询线段树维护的值，碎块暴力计算。然后撤销的话只需要重构撤销区间所在的块即可。
然后你就会得到一个二十分到五十分的做法。
考虑优化，发现主要是因为空间太大了导致的，所以你可以写动态开点线段树，同时你也可以将修改区间离散化。但是注意，有一些点可能在离散化的过程中被吞掉，那你就在离散化的时候再加入一个区间，这个区间向左或者向右平移一格，这样子的话不存在的点就等效作用在这些你新加的区间了。
然后你再卡个一两个小时的常数就可以过了，具体的，你可以使用并查集跳过一些操作，将一些函数去掉直接放到主函数里面。并且调整块的长度，再选一个夜深人静的时候提交。
# include <bits/stdc++.h>
# define lid tr[id].l
# define rid tr[id].r
# define sil static inline
using namespace std;
const int N = 150001 , M = 1005;
const long long p = 998244353;
int n , m , qop[N] , ql[N] , qr[N] , qd[N] , qp[N];
int fa[N];
int g[M][M * 4 + 5] , f[M];
char buf[1 << 20],*p1,*p2;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2)?0:*p1++)
sil int read(){int x = 0,w = 1;char c = 0;while(c < '0' || c > '9'){if(c == '-')w = -1;c = getc();}while(c <= '9' && c >= '0'){x = (x << 1) + (x << 3) + (c ^ 48);c = getc();}return x * w;}
sil void print(register long long x){if(x < 0){x = -x;putchar('-');}if(x > 9)print(x / 10);putchar(x % 10 + 48);}
struct kdtree {
int l , r ;
long long val , add , mul , a , b;
bool cl;
} tr[N * 20];
int tot;
sil int fd (int x) { return fa[x] == x ? x : fa[x] = fd(fa[x]); }
sil void make (const int &id , const int &adtag , const int &mltag , const bool &cl) {
if (cl) tr[id].a = tr[id].mul = 1 , tr[id].b = tr[id].add = 0 , tr[id].cl = true;
if (mltag != 1) {
tr[id].a = (tr[id].a * mltag % p) % p , tr[id].b = (tr[id].b * mltag % p) % p;
tr[id].add = (tr[id].add* mltag % p) % p , tr[id].mul = (tr[id].mul * mltag % p) % p;
}
if (adtag != 0) {
tr[id].b = (tr[id].b + adtag);
tr[id].b = (tr[id].b > p ? tr[id].b - p : tr[id].b);
tr[id].add = (tr[id].add + adtag);
tr[id].add = (tr[id].add > p ? tr[id].add - p : tr[id].add);
}
return ;
}
sil int build (int l ,int r) {
int id = ++tot;
tr[id].mul = tr[id].a = 1;
if (l == r) return id;
int mid = (l + r) >> 1;
tr[id].l = build(l,mid),tr[id].r = build(mid + 1,r);
return id;
}
sil void Mul_cg (int id,const int& l,const int& r,int k,int L,int R) {
if (L >= l && R <= r) return make (id , 0 , k , 0) , void () ;
make (lid , tr[id].add , tr[id].mul , tr[id].cl) ;
make (rid , tr[id].add , tr[id].mul , tr[id].cl) ;
tr[id].mul = 1 , tr[id].add = tr[id].cl = 0;
int mid = (L + R) >> 1;
if (l <= mid) Mul_cg(lid,l,r,k,L,mid);
if (r > mid) Mul_cg(rid,l,r,k,mid+1,R);
}
sil void Add_cg (int id,const int& l,const int& r,const int& k,int L,int R) {
if (L >= l && R <= r) return make (id , k , 1 , 0) , void () ;
make (lid , tr[id].add , tr[id].mul , tr[id].cl) ;
make (rid , tr[id].add , tr[id].mul , tr[id].cl) ;
tr[id].mul = 1 , tr[id].add = tr[id].cl = 0;
int mid = (L + R) >> 1;
if (l <= mid) Add_cg(lid,l,r,k,L,mid);
if (r > mid) Add_cg(rid,l,r,k,mid+1,R);
}
sil void query (int id,const int& pos,int L,int R,long long &val) {
if (L == R) {val = (tr[id].a % p * 1ll * val + tr[id].b) , val = (val > p ? val - p : val); return ;}
int mid = (L + R) >> 1;
make (lid , tr[id].add , tr[id].mul , tr[id].cl) ;
make (rid , tr[id].add , tr[id].mul , tr[id].cl) ;
tr[id].mul = 1 , tr[id].add = tr[id].cl = 0;
if (pos <= mid) return query(lid,pos,L,mid,val) , void ();
else return query(rid,pos,mid+1,R,val) , void ();
}
int block , st[M] , ed[M] , sz , root[N] , pos[N];
signed main () {
n = read() , m = read();
for (int i = 1;i <= m;++i) {
qop[i] = read();
if (qop[i] <= 2) ql[i] = read() , qr[i] = read() , qd[i] = read() , qd[i] = (qd[i] > p ? qd[i] - p : qd[i]);
if (qop[i] >= 3) qp[i] = read();
}
iota (fa + 1 , fa + m + 2 , 1);
block = max ((int)sqrt (1.50066 * m) , 77);
sz = m / block;
for (int i = 1;i <= block;++i) st[i] = (i - 1) * sz + 1 , ed[i] = i * sz;
ed[block] = m;
for (int i = 1;i <= block;++i) for (int j = st[i];j <= ed[i];++j) pos[j] = i;
for (int j = 1;j <= block;++j) {
g[j][++f[j]] = n;
for (int i = st[j];i <= ed[j];++i) {
if (qop[i] <= 2) {
g[j][++f[j]] = ql[i] , g[j][++f[j]] = qr[i] ;
g[j][++f[j]] = ql[i] - 1 , g[j][++f[j]] = qr[i] - 1;
}
}
sort (g[j] + 1 , g[j] + f[j] + 1);
f[j] = unique (g[j] + 1 , g[j] + f[j] + 1) - g[j] - 1;
for (int i = st[j];i <= ed[j];++i) {
if (qop[i] <= 2) {
ql[i] = lower_bound (g[j] + 1 , g[j] + f[j] + 1 , ql[i]) - g[j];
qr[i] = lower_bound (g[j] + 1 , g[j] + f[j] + 1 , qr[i]) - g[j];
}
else fa[i] = fd(i + 1);
}
root[j] = build (1 , f[j]);
}
for (int T = 1;T <= m;++T) {
if (qop[T] == 1) Add_cg (root[pos[T]] , ql[T] , qr[T] , qd[T] , 1 , f[pos[T]]);
else if (qop[T] == 2) Mul_cg (root[pos[T]] , ql[T] , qr[T] , qd[T] , 1 , f[pos[T]]);
else if (qop[T] == 3) {
long long ans = 0;
for (int i = 1;i < pos[T];++i) query (root[i] , lower_bound (g[i] + 1 , g[i] + f[i] + 1 , qp[T]) - g[i] , 1 , f[i] , ans) , ans %= p;
for (int i = fd(st[pos[T]]);i <= T;i = fd(i + 1)) {
int fqp = lower_bound (g[pos[T]] + 1 , g[pos[T]] + f[pos[T]] + 1 , qp[T]) - g[pos[T]];
if (qop[i] == 1 && ql[i] <= fqp && fqp <= qr[i]) ans = (ans + qd[i]) , ans = (ans > p ? ans - p : ans);
if (qop[i] == 2 && ql[i] <= fqp && fqp <= qr[i]) ans = (ans * qd[i]) , ans %= p;
}
print(ans % p) , putchar('\n');
}
else {
fa[qp[T]] = fd(qp[T] + 1);
make (root[pos[qp[T]]] , 0 , 1 , 1);
int L = fd(st[pos[qp[T]]]) , R = min (ed[pos[qp[T]]] , T);
for (int i = L;i <= R;i = fd(i + 1)) {
if (qop[i] == 1) Add_cg (root[pos[qp[T]]] , ql[i] , qr[i] , qd[i] , 1 , f[pos[qp[T]]]);
if (qop[i] == 2) Mul_cg (root[pos[qp[T]]] , ql[i] , qr[i] , qd[i] , 1 , f[pos[qp[T]]]);
}
}
}
return 0;
}
/*
1 . 2 操作加法打标记，乘法扩大加法标记在打标记
3 直接做
4 按照时间轴进行分块（第几次操作）
接下来是老师讲的：
对询问分块，对每个块开一个线段树处理1 . 2操作 （空间开不下可以开大一点块，这样少开一点线段树）
*/