?

? ? 假設我們可以對每個位置快速維護一個數組，記錄每個位置有哪些值是已經出現了的，哪些值是沒有出現的，這樣就可以決定修改的時候到底是 *2 還是 +1了。

?

? ? 但是很可惜，并不存在功能這么強大的數組，所以只能另尋方法啦。。。。

?

? ? 因為修改總是連續的一段的，所以我們可以發現，對于每個數值來說，被它覆蓋的位置也是一段一段的，并且所有數的段數之和<=總的操作數(因為還會發生一些段的合并)。

?

? ? 所以我們可以對每個數維護一個端點集合set，每次修改的時候就暴力插入一段區間，看一看可以產生多少次合并。

?

? ? 這樣的話，雖然一次修改的復雜度可能會十分之大，但是因為一個端點在貢獻一次合并之后就被從 set 里刪去了(一次合并只會對應線段樹中的一次區間修改)，并且每次最多增加兩個端點，所以可以證明最后總的復雜度是 O( M * log (N) )，常數略大。。。

?

??? （并且用set維護每個數的區間的時候細節特別多，一定要想清楚了再去寫）

?

? ? (rank 22/212)

?

?

?

Discription

In the School of Magic in Dirtpolis a lot of interesting objects are studied on Computer Science lessons.

Consider, for example, the magic multiset. If you try to add an integer to it that is already presented in the multiset, each element in the multiset duplicates. For example, if you try to add the integer?22?to the multiset?{1,2,3,3}{1,2,3,3}, you will get?{1,1,2,2,3,3,3,3}{1,1,2,2,3,3,3,3}.

If you try to add an integer that is not presented in the multiset, it is simply added to it. For example, if you try to add the integer?44?to the multiset?{1,2,3,3}{1,2,3,3}, you will get?{1,2,3,3,4}{1,2,3,3,4}.

Also consider an array of?nn?initially empty magic multisets, enumerated from?11?to?nn.

You are to answer?qq?queries of the form "add an integer?xx?to all multisets with indices?l,l+1,…,rl,l+1,…,r" and "compute the sum of sizes of multisets with indices?l,l+1,…,rl,l+1,…,r". The answers for the second type queries can be large, so print the answers modulo?998244353998244353.

Input

The first line contains two integers?nn?and?qq?(1≤n,q≤2?1051≤n,q≤2?105)?— the number of magic multisets in the array and the number of queries, respectively.

The next?qq?lines describe queries, one per line. Each line starts with an integer?tt(1≤t≤21≤t≤2)?— the type of the query. If?tt?equals?11, it is followed by three integers?ll,?rr,?xx?(1≤l≤r≤n1≤l≤r≤n,?1≤x≤n1≤x≤n) meaning that you should add?xx?to all multisets with indices from?ll?to?rr?inclusive. If?tt?equals?22, it is followed by two integers?ll,?rr?(1≤l≤r≤n1≤l≤r≤n) meaning that you should compute the sum of sizes of all multisets with indices from?ll?to?rr?inclusive.

Output

For each query of the second type print the sum of sizes of multisets on the given segment.

The answers can be large, so print them modulo?998244353998244353.

Examples

Input 4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4 Output 10 Input 3 7
1 1 1 3
1 1 1 3
1 1 1 2
1 1 1 1
2 1 1
1 1 1 2
2 1 1 Output 4
8

Note

In the first example after the first two queries the multisets are equal to?[{1,2},{1,2},{},{}][{1,2},{1,2},{},{}], after the third query they are equal to?[{1,1,2,2},{1,1,2,2},{1},{1}][{1,1,2,2},{1,1,2,2},{1},{1}].

In the second example the first multiset evolves as follows:

{}→{3}→{3,3}→{2,3,3}→{1,2,3,3}→{1,1,2,2,3,3,3,3}{}→{3}→{3,3}→{2,3,3}→{1,2,3,3}→{1,1,2,2,3,3,3,3}.

?

?

?

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=200005,ha=998244353; #define lc (o<<1) #define mid (l+r>>1) #define rc ((o<<1)|1) inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;} inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;} struct node{int p,id;bool operator <(const node &u)const{return p==u.p?id<u.id:p<u.p;} }; set<node> s[maxn]; set<node> :: iterator it,her; int d[maxn*4],tag[maxn*4],sum[maxn*4]; int n,m,Q,le,ri,w,len[maxn*4],ans,opt;inline void maintain(int o){ sum[o]=add(sum[lc],sum[rc]);}inline void work(int o,int der){ADD(tag[o],der);ADD(sum[o],der*(ll)len[o]%ha); }inline void mul(int o,int der){d[o]=d[o]*(ll)der%ha;tag[o]=tag[o]*(ll)der%ha;sum[o]=sum[o]*(ll)der%ha; }inline void pushdown(int o){if(d[o]!=1){mul(lc,d[o]),mul(rc,d[o]);d[o]=1;}if(tag[o]){work(lc,tag[o]),work(rc,tag[o]);tag[o]=0;} }void build(int o,int l,int r){d[o]=1,len[o]=r-l+1;if(l==r) return;build(lc,l,mid);build(rc,mid+1,r); }void umul(int o,int l,int r){if(l>=le&&r<=ri){ mul(o,2); return;}pushdown(o);if(le<=mid) umul(lc,l,mid);if(ri>mid) umul(rc,mid+1,r);maintain(o); }void uadd(int o,int l,int r){if(l>=le&&r<=ri){ work(o,w); return;}pushdown(o);if(le<=mid) uadd(lc,l,mid);if(ri>mid) uadd(rc,mid+1,r);maintain(o); }void query(int o,int l,int r){if(l>=le&&r<=ri){ ADD(ans,sum[o]); return;}pushdown(o);if(le<=mid) query(lc,l,mid);if(ri>mid) query(rc,mid+1,r); }void Change(int num,int L,int R){ set<node> &S=s[num];int fl=L,fr=R;it=S.lower_bound((node){L,0});for(w=1;L<=R;it=S.lower_bound((node){L,0})){if(it==S.end()){le=L,ri=R,uadd(1,1,n);break;}else if(it->id){le=L,ri=min(it->p,R),umul(1,1,n);L=ri+1;if(R>=it->p) S.erase(it);}else{le=L,ri=min(it->p-1,R);if(le<=ri) uadd(1,1,n);L=ri+1;if(R>=it->p) S.erase(it);}}it=S.lower_bound((node){fl,0});her=S.lower_bound((node){fr,1});if(it==S.begin()||(--it)->id) S.insert((node){fl,0});if(her==S.end()||!her->id) S.insert((node){fr,1}); }inline void solve(){build(1,1,n);while(Q--){scanf("%d",&opt);if(opt==1){scanf("%d%d%d",&le,&ri,&w);Change(w,le,ri);}else{scanf("%d%d",&le,&ri),ans=0;query(1,1,n),printf("%d\n",ans);}} }int main(){scanf("%d%d",&n,&Q);solve();return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/9110639.html

總結

以上是生活随笔為你收集整理的CodeForces - 981G Magic multisets的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。