牛逼题。
先考虑 \(l\le 10^5,10^5+1\le r\) 的部分分：一种方法是线段树，即因为左右端点是独立的，因此对左右端点各维护一个权值线段树表示有多少个区间以这个值为左 / 右端点，这样对于修改，左端点的部分相当于先查询 \(\le l\) 的数的个数，然后将它们都挂到 \(l\) 上，最后把 \(<l\) 的部分清空了，右端点也同理。对于查询就线段树上每个节点维护 \(\sum cnt_i\) 和 \(\sum cnt_i·i\) 即可。
但是这种做法不容易推广到正解的部分，因此再说一个与正解有点关系的使用堆维护这部分的做法。因为你相当于将所有区间左端点对 \(L\) 取 \(\max\)，以及将所有区间右端点对 \(R\) 取 \(\min\)。考虑对左右端点各维护一个堆，同时维护两个并查集，将左右端点相同的线段缩到并查集同一等价类内，然后堆内存储若干个 pair 表示所有出现过的左 / 右端点和其在并查集中的根节点，这样就可以在均摊 \(O(1)\) 的时间内处理修改。查询是类似的，维护 \(\sum cnt_i\) 和 \(\sum cnt_i·i\)，这里可以树状数组。
接下来考虑正解的部分。建一棵权值线段树，线段树每个节点 \([L,R]\) 上使用上述所说的基于堆和并查集的数据结构维护当前区间集中所有跨 \(mid\) 的区间，然后一次操作的影响：
- 插入操作：找到满足 \(L\le l\le mid<r\le R\) 的区间 \([L,R]\)，然后往这个节点的数据结构里插入区间 \([l,r]\)。
- 修改操作：类比在线段树上进行区间查询，考虑当前线段树上区间 \([L,R]\) 与查询区间 \([l,r]\) 的关系：
- 无交，返回。
- \([L,R]\in[l,r]\)，返回。
- \(l\le mid<r\)，将这个节点上所有区间左端点对 \(l\) 取 \(\max\)，右端点对 \(r\) 取 \(\min\)，使用上面的方法处理即可。
- \(r\le mid\) 或者 \(l>mid\)，二者是等价的，这里考虑前者。操作这个区间对这个节点上的区间的影响是，如果这个区间上的节点与 \([l,r]\) 有交，那么操作完以后它就完全属于左半边了，它就不能待在这个节点上，得往左儿子走。而容易证明当前节点上的区间 \([l',r']\) 与 \([l,r]\) 有交当且仅当 \(l'\le r\)，因此这里我们采取一种简单粗暴的方法：不断 pop 掉左端点对应的堆里的最小元素知道它 \(>r\)，对于被 pop 掉的元素，考察其对应并查集中所有区间，将其插入左子树内。类比李超线段树，每个区间最多移动 \(\log\) 次，所以这里复杂度是对的。
- 查询操作：情况类似。由于这个修改操作是全局的，因此树状数组只用开一个（即，不用对每个节点都开一个）。
时间复杂度 \((n+q)\log^2n\)。代码实现比较复杂。
const int MAXN=2e5;
const int MAXP=MAXN<<6;
int qu,typ;ll lstans;
struct fenwick{
ll t[MAXN+5];
void add(int x,ll v){for(int i=x;i<=MAXN;i+=(i&(-i)))t[i]+=v;}
ll query(int x){ll ret=0;for(int i=x;i;i&=(i-1))ret+=t[i];return ret;}
}T1,T2,T3,T4;
void addl(int x,int v){T1.add(x,v),T2.add(x,1ll*v*x);}
void addr(int x,int v){T3.add(x,v),T4.add(x,1ll*v*x);}
ll query(int l,int r){
ll res=0;
res+=T4.query(r)+1ll*r*(T3.query(MAXN)-T3.query(r));
res-=T2.query(MAXN)-T2.query(l)+1ll*l*T1.query(l);
res-=T4.query(l-1)-1ll*l*T3.query(l-1);
res-=1ll*r*(T1.query(MAXN)-T1.query(r))-(T2.query(MAXN)-T2.query(r));
return res;
}
struct node{
int l,r;priority_queue<pii>qr;
priority_queue<pii,vector<pii>,greater<pii> >ql;
}s[MAXN*4+5];
bool vis[MAXP+5];
int mch[MAXP+5],f[MAXP+5],val[MAXP+5],ncnt,alive[MAXP+5],siz[MAXP+5];
vector<int>g[MAXP+5];
int find(int x){return (!f[x])?x:f[x]=find(f[x]);}
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r)return;int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void insert(int k,int l,int r){
int mid=s[k].l+s[k].r>>1;
if(r<=mid)insert(k<<1,l,r);
else if(l>mid)insert(k<<1|1,l,r);
else{
int P=++ncnt,Q=++ncnt;val[P]=l;val[Q]=r;mch[P]=Q;mch[Q]=P;
alive[P]=alive[Q]=siz[P]=siz[Q]=1;s[k].ql.push(mp(l,P));s[k].qr.push(mp(r,Q));
}
}
int merge(int x,int y){
if(!x||!y)return x+y;x=find(x);y=find(y);if(x==y)return x;
if(siz[x]<siz[y])swap(x,y);f[y]=x;siz[x]+=siz[y];g[x].pb(y);
return x;
}
void insl(int k,int l,int r,int p,int L){
if(alive[p]){
int q=mch[p],R=val[find(q)];alive[p]=alive[q]=0;
siz[find(p)]--;siz[find(q)]--;
int nwl=max(L,l),nwr=min(R,r);
addl(L,-1);addr(R,-1);
if(nwl!=nwr)addl(nwl,1),addr(nwr,1),insert(k,nwl,nwr);
}
for(int pp:g[p])insl(k,l,r,pp,L);
}
void insr(int k,int l,int r,int p,int R){
if(alive[p]){
int q=mch[p],L=val[find(q)];alive[p]=alive[q]=0;
siz[find(p)]--;siz[find(q)]--;
int nwl=max(L,l),nwr=min(R,r);
addl(L,-1);addr(R,-1);
if(nwl!=nwr)addl(nwl,1),addr(nwr,1),insert(k,nwl,nwr);
}
for(int pp:g[p])insr(k,l,r,pp,R);
}
void modify(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r)return;
int mid=s[k].l+s[k].r>>1;
if(r<=mid){
while(!s[k].ql.empty()){
pii p=s[k].ql.top();if(p.fi>r)break;
insl(k<<1,l,r,p.se,p.fi);s[k].ql.pop();
}
modify(k<<1,l,r);
}else if(l>mid){
while(!s[k].qr.empty()){
pii p=s[k].qr.top();if(p.fi<l)break;
insr(k<<1|1,l,r,p.se,p.fi);s[k].qr.pop();
}
modify(k<<1|1,l,r);
}else{
int nd=0;
while(!s[k].ql.empty()){
pii p=s[k].ql.top();if(p.fi>=l)break;
addl(p.fi,-siz[p.se]);nd=merge(nd,p.se);
s[k].ql.pop();
}
if(nd)val[nd]=l,addl(l,siz[nd]),s[k].ql.push(mp(l,nd));
nd=0;
while(!s[k].qr.empty()){
pii p=s[k].qr.top();if(p.fi<=r)break;
addr(p.fi,-siz[p.se]);nd=merge(nd,p.se);
s[k].qr.pop();
}
if(nd)val[nd]=r,addr(r,siz[nd]),s[k].qr.push(mp(r,nd));
modify(k<<1,l,mid);modify(k<<1|1,mid+1,r);
}
}
int main(){
// freopen("yy.in","r",stdin);freopen("yy.out","w",stdout);
scanf("%d%d",&qu,&typ);build(1,1,MAXN);
for(int i=1;i<=qu;i++){
int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
x=(x+typ*lstans)%(MAXN+1);y=(y+typ*lstans)%(MAXN+1);
if(x>y)swap(x,y);
if(opt==1){
if(x==y)continue;addl(x,1);addr(y,1);
insert(1,x,y);
}else if(opt==2)modify(1,x,y);
else printf("%lld\n",lstans=query(x,y));
}
return 0;
}