fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ar3 = array<int,3>;
  6.  
  7. const int mxN = (int)2e5+2;
  8. const int INF = (int)1e9+1;
  9. const ll MOD = (ll)1e9+7;
  10. const int sqMX = 1<<15;
  11. ll p2[2][sqMX];
  12.  
  13. ll poww2(ll b){ return (p2[1][b/sqMX]*p2[0][b&(sqMX-1)])%MOD; }
  14.  
  15. void preComputePowers(){
  16. 	p2[0][0]=p2[1][0]=1;
  17. 	for(int i = 1; i < sqMX; i++)
  18. 		p2[0][i]=(p2[0][i-1]*2)%MOD;
  19. 	ll bigSq = (p2[0][sqMX-1]*2)%MOD;
  20. 	for(int i = 1; i < sqMX; i++)
  21. 		p2[1][i]=(p2[1][i-1]*bigSq)%MOD;
  22. }
  23.  
  24. template<int MX, int SZ>
  25. struct SparseLazySegTree{
  26. 	bitset<SZ> lz;
  27. 	ar3 seg[SZ], emp;
  28. 	int L[SZ], R[SZ], IND;
  29.  
  30. 	void init(){
  31. 		lz.reset(); IND = 1; 
  32.         memset(L,0,sizeof(L));
  33.         memset(R,0,sizeof(R));
  34.         seg[1]={0,0,MX}; emp={0,0,0};
  35. 	}
  36.  
  37. 	void apply(int p, int l, int r){
  38. 		int sz = seg[p][2];
  39. 		seg[p][0]=sz-seg[p][0];
  40.         ll xd =poww2(sz)-1;
  41.         xd+=MOD-(ll)seg[p][1];
  42.         xd%=MOD; seg[p][1]=xd;
  43. 		lz[p]=1-lz[p];
  44. 	}
  45.  
  46. 	void prop(int p, int l, int r){
  47. 		if(!p or !lz[p] or l==r) return; int mid = (l+r)/2;
  48. 		if(!L[p]) L[p]=++IND,seg[L[p]]=ar3({0,0,mid-l+1});
  49. 		if(!R[p]) R[p]=++IND,seg[R[p]]=ar3({0,0,r-mid});
  50. 		apply(L[p],l,mid); apply(R[p],mid+1,r); lz[p]=0;
  51. 	}
  52.  
  53. 	ar3 comb(ar3 &a, ar3 &b){
  54. 		ar3 c = a; c[0]+=b[0]; c[2]+=b[2];
  55. 		ll xd = a[1]; xd*=poww2(b[2]); xd+=(ll)b[1]; 
  56. 		xd%=MOD; c[1] = xd; return c;
  57. 	}
  58.  
  59. 	void updtoggle(int i, int j, int p=1, int l=1, int r=MX){
  60. 		if(i>r or j<l or i>j or !p) return; prop(p,l,r);
  61. 		if(i<=l and r<=j){ apply(p,l,r); return; }
  62. 		int mid = (l+r)/2;
  63. 		if(!L[p]) L[p]=++IND,seg[L[p]]=ar3({0,0,mid-l+1});
  64. 		if(!R[p]) R[p]=++IND,seg[R[p]]=ar3({0,0,r-mid});
  65. 		updtoggle(i,j,L[p],l,mid);
  66. 		updtoggle(i,j,R[p],mid+1,r);
  67. 		seg[p] = comb(seg[L[p]],seg[R[p]]);
  68. 	}
  69.  
  70. 	ar3 query(int i, int j, int p=1, int l=1, int r=MX){
  71. 		if(i>r or j<l or i>j or !p) return emp; prop(p,l,r);
  72. 		if(i<=l and r<=j) return seg[p];
  73. 		int mid = (l+r)/2;
  74. 		auto le = query(i,j,L[p],l,mid);
  75. 		if(!R[p]) return le;
  76. 		auto ri = query(i,j,R[p],mid+1,r);
  77. 		if(!L[p]) return ri;
  78. 		return comb(le,ri);
  79. 	}
  80.  
  81.     int findKthZero(int k, int p=1, int l=1, int r=MX){
  82.         if(l==r) return l; prop(p,l,r);
  83.         int mid = (l+r)/2;
  84.         if(!L[p]) return l+k-1;
  85.         int num = mid-l+1-seg[L[p]][0];
  86.         if(num<k){
  87.             if(!R[p]) return mid+k-num;
  88.             return findKthZero(k-num,R[p],mid+1,r);
  89.         }
  90.         return findKthZero(k,L[p],l,mid);
  91.     }
  92. };
  93.  
  94. SparseLazySegTree<INF,__lg(INF)*mxN*2> seg;
  95. ll n, m, q, l, r, k, ans;
  96.  
  97. int main(){
  98.     ios_base::sync_with_stdio(false); cin.tie(0);
  99.     cin >> n >> m >> q; 
  100.     preComputePowers(); seg.init();
  101.     while(m--) cin >> l >> r, seg.updtoggle(l,r);
  102. 	while(q--){
  103. 		cin >> l >> r >> k;
  104. 		auto cur = seg.query(l,r);
  105. 		if(cur[0]>=k) ans = (poww2(k)-1+MOD)%MOD;
  106. 		else{
  107.             int L = seg.findKthZero(r-seg.query(1,r)[0]-(k-cur[0])+1);
  108. 			auto lol = seg.query(L,r);
  109. 			ans = poww2(cur[0]-lol[0])-1;
  110. 			ans*=poww2(r-L+1); ans+=(ll)lol[1]; ans%=MOD;
  111. 		}
  112. 		cout << ans << "\n";
  113. 	}
  114. }
  115.  
Success #stdin #stdout 0.02s 99020KB
comments (?)
stdin
copy 
5 4 6
1 3
4 5
2 4
3 3
1 5 2
1 5 4
1 5 5
2 5 3
2 3 2
3 4 2
stdout
copy 
3
13
21
5
1
2
https://ideone.com/UkLwbB
Usaco Gold 2025 Feb P2
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!