• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

Shiam7777777 Mar 20th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
4. #define ll long long
5. #define ld double
6. #define llu long long unsigned
7.
8. #define mx 3000001
9.
10. int arr[ mx ];
11.
12. struct info {
13.     int prop, sum0 , sum1;
14. } tree[mx * 3];
15.
16. void init(int node, int b, int e)
17. {
18.     if (b == e) {
19.         tree[node].sum0 = 1;
20.         tree[node].sum1 = 0;
21.         return;
22.     }
23.     int Left = node << 1;
24.     int Right = ( node << 1 ) + 1;
25.     int mid = (b + e) >> 1;
26.     init(Left, b, mid);
27.     init(Right, mid + 1, e);
28.     tree[node].sum0 = tree[Left].sum0 + tree[Right].sum0;
29.     tree[node].sum1 = tree[Left].sum1 + tree[Right].sum1;
30. }
31.
32. void update(int node, int b, int e, int i, int j, int x)
33. {
34.     if (i > e || j < b)
35.         return;
36.     if (b >= i && e <= j)
37.     {
38.         swap( tree[node].sum0 , tree[node].sum1 );
39. //        tree[node].sum += ((e - b + 1) * x);    //  adding sum
40.         tree[node].prop += x;
41.         return;
42.     }
43.     int Left = node << 1;
44.     int Right = (node << 1) + 1;
45.     int mid = (b + e) >> 1;
46.     update(Left, b, mid, i, j, x);
47.     update(Right, mid + 1, e, i, j, x);
48.     tree[node].sum0 = tree[Left].sum0 + tree[Right].sum0;
49.     tree[node].sum1 = tree[Left].sum1 + tree[Right].sum1;
50.     int rot = tree[node].prop % 2;
51.     if( rot )
52.     {
53.         swap( tree[node].sum0 , tree[node].sum1 );
54.     }
55. }
56.
57. info query(int node, int b, int e, int i, int j, int carry = 0)
58. {
59.     if (i > e || j < b)
60.     {
61.         info tmp;
62.         tmp.prop = 0;
63.         tmp.sum0 = 0;
64.         tmp.sum1 = 0;
65.         return tmp;
66.     }
67.
68.
69.     if (b >= i and e <= j)
70.     {
71.         info tr;
72.         tr = tree[node];
73.         int rot = carry % 2;
74.         if( rot )
75.         {
76.             swap( tr.sum0 , tr.sum1 );
77.         }
78.         return tr;
79. //        return tree[node].sum + carry * (e - b + 1);
80.     }
81.
82.     int Left = node << 1;
83.     int Right = (node << 1) + 1;
84.     int mid = (b + e) >> 1;
85.
86.     info p1 = query(Left, b, mid, i, j, carry + tree[node].prop);
87.     info p2 = query(Right, mid + 1, e, i, j, carry + tree[node].prop);
88.
89.     info tmp;
90.     tmp.sum0 = p1.sum0 + p2.sum0;
91.     tmp.sum1 = p1.sum1 + p2.sum1;
92.     tmp.prop = 0;
93.     return tmp;
94. //    return p1 + p2;
95. }
96.
97. int main()
98. {
99.     fast;
100.     int n , q;
101.     cin>>n>>q;
102.     init( 1 , 1 , n );
103.     while( q-- )
104.     {
105.         int t;
106.         cin>>t;
107.         if( t == 0 )
108.         {
109.             int i , j;
110.             cin>>i>>j;
111.             update( 1 , 1 , n , i+1 , j+1 , 1 );
112.         }
113.         else if( t == 1 )
114.         {
115.             int i , j;
116.             cin>>i>>j;
117.             info tmp;
118.             tmp = query( 1 , 1 , n , i+1 , j+1 );
119.             cout<<tmp.sum1<<endl;
120.         }
121.     }
122.     return 0;
123. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top