【UOJ291】【ZJOI2017】树状数组

Author Avatar
q234rty 3月 28, 2017

cdq分治+线段树即可。

题解请戳InvUsr的博客

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXSIZE=30000020;
  4. const int maxn=100001;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. void init(){
  8.     #ifdef LOCAL
  9.         freopen("291.txt","r",stdin);
  10.     #endif // LOCAL
  11.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  12.     bufpos=0;
  13. }
  14. int readint(){
  15.     int val=0;
  16.     for(;!isdigit(buf[bufpos]);bufpos++);
  17.     for(;isdigit(buf[bufpos]);bufpos++)
  18.         val=val*10+buf[bufpos]-'0';
  19.     return val;
  20. }
  21. typedef long long ll;
  22. const ll mod=998244353;
  23. ll power(ll x,ll y){
  24. 	ll t=x,res=1;
  25. 	while(y){
  26. 		if (y%2)
  27. 			(res*=t)%=mod;
  28. 		(t*=t)%=mod;
  29. 		y/=2;
  30. 	}
  31. 	return res;
  32. }
  33. ll pls(ll x,ll y){
  34.     return (x*(1-y)+(1-x)*y)%mod;
  35. }
  36. struct atom{
  37. 	ll prob1,prob2;
  38. 	atom(){
  39. 	    prob1=prob2=0;
  40. 	}
  41. 	atom(ll prob1,ll prob2):prob1(prob1),prob2(prob2){}
  42. 	atom operator +(const atom& rhs)const{
  43. 		return atom(pls(prob1,rhs.prob1),pls(prob2,rhs.prob2));
  44. 	}
  45. 	atom& operator +=(const atom& rhs){
  46.         return *this=(*this)+rhs;
  47. 	}
  48. };
  49. struct segtree{
  50.     int n;
  51.     atom t[maxn*4];
  52.     int w[maxn*20];
  53.     void init(int n){
  54.         this->n=n;
  55.     }
  56.     int cur;
  57.     void clear(){
  58.         for(int i=1;i<=cur;i++)
  59.             t[w[i]].prob1=t[w[i]].prob2=0;
  60.         cur=0;
  61.     }
  62.     int p;
  63.     atom v;
  64.     void update(int o,int l,int r){
  65.         if (l==r){
  66.             t[w[++cur]=o]+=v;
  67.             return;
  68.         }
  69.         int mid=(l+r)/2;
  70.         if (p<=mid)
  71.             update(o*2,l,mid);
  72.         else update(o*2+1,mid+1,r);
  73.         t[w[++cur]=o]=t[o*2]+t[o*2+1];
  74.     }
  75.     void update(int p,atom& v){
  76.         this->p=p;
  77.         this->v=v;
  78.         update(1,1,n);
  79.     }
  80.     int ql,qr;
  81.     atom query(int o,int l,int r){
  82.         if (ql<=l && qr>=r){
  83.             //printf("on %d %d %lld\n",l,r,t[o].prob1);
  84.             return t[o];
  85.         }
  86.         int mid=(l+r)/2;
  87.         atom res;
  88.         if (ql<=mid)
  89.             res+=query(o*2,l,mid);
  90.         if (qr>mid)
  91.             res+=query(o*2+1,mid+1,r);
  92.         return res;
  93.     }
  94.     atom query(int l,int r){
  95.         ql=l,qr=r;
  96.         return query(1,1,n);
  97.     }
  98. }t;
  99. struct query{
  100. 	int typ,p,l,r;
  101. 	atom w;
  102. }a[maxn],b[maxn];
  103. bool comp1(const query& x,const query& y){
  104. 	return x.l==y.l?x.typ<y.typ:x.l<y.l;
  105. }
  106. bool comp2(const query& x,const query& y){
  107.     return x.r==y.r?x.typ<y.typ:x.r>y.r;
  108. }
  109. ll ans[maxn];
  110. int n;
  111. void cdq(int l,int r){
  112. 	if (l==r)
  113. 		return;
  114. 	int mid=(l+r)/2;
  115. 	cdq(l,mid);
  116. 	cdq(mid+1,r);
  117. 	int cur=0;
  118. 	for(int i=l;i<=mid;i++)
  119. 		if (a[i].typ==1)
  120. 			b[++cur]=a[i];
  121. 	for(int i=mid+1;i<=r;i++)
  122. 		if (a[i].typ==2)
  123. 			b[++cur]=a[i];
  124.     t.clear();
  125. 	sort(b+1,b+cur+1,comp1);
  126. 	for(int i=1;i<=cur;i++){
  127.         if (!b[i].l)
  128.             continue;
  129.         if (b[i].typ==1){
  130.             //printf("%d %d %lld\n",b[i].l,b[i].r,b[i].w.prob1);
  131.             t.update(b[i].r,b[i].w);
  132.         }else{
  133.             atom x=t.query(b[i].l,b[i].r-1),y=t.query(b[i].r,n);
  134.             //if (b[i].l==1 && b[i].r==5)
  135.                 //printf("qaq=%lld\n",x.prob1);
  136.             ans[b[i].p]=pls(ans[b[i].p],pls(x.prob1,y.prob2));
  137.         }
  138. 	}
  139. 	sort(b+1,b+cur+1,comp2);
  140. 	t.clear();
  141. 	for(int i=1;i<=cur;i++){
  142.         if (b[i].typ==1)
  143.             t.update(b[i].l,b[i].w);
  144.         else ans[b[i].p]=pls(ans[b[i].p],t.query(b[i].l+1,b[i].r).prob1);
  145. 	}
  146. }
  147. bool flag[maxn];
  148. bool isq[maxn];
  149. int main(){
  150. 	init();
  151. 	n=readint();
  152. 	int m=readint();
  153. 	t.init(n);
  154. 	for(int i=1;i<=m;i++){
  155.         a[i].typ=readint(),a[i].l=readint(),a[i].r=readint();
  156.         a[i].p=i;
  157.         if (a[i].typ==1){
  158.             ll t=power(a[i].r-a[i].l+1,mod-2);
  159.             a[i].w=atom(t,t*2%mod);
  160.             flag[i]=!flag[i-1];
  161.         }else a[i].l--,flag[i]=flag[i-1],isq[i]=true;
  162. 	}
  163. 	//puts("WTF");
  164. 	cdq(1,m);
  165. 	for(int i=1;i<=m;i++){
  166.         if (!isq[i])
  167.             continue;
  168.         //printf("%lld\n",ans[i]);
  169.         if (a[i].l || !flag[i])
  170.             ans[i]=(1-ans[i])%mod;
  171.         printf("%lld\n",(ans[i]+mod)%mod);
  172. 	}
  173. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/03/28/uoj291/

隐藏