API tools faq
paste
Sayach8

Untitled

Sayach8
Oct 9th, 2021
16
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.46 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #define gp __gnu_pbds
  4. #define iset(T) gp::tree<T,gp::null_type,less<T>,gp::rb_tree_tag,gp::tree_order_statistics_node_update>
  5. using namespace std;
  6.  
  7. #define SQ(x) ((x)*(x))
  8. #define u unsigned
  9. #define ull unsigned long long
  10. #define ll long long
  11. #define ld long double
  12. #define test(x) cerr<<"here "<<#x<<endl;
  13. #define putpls(x) #x
  14. #define casing(x,y) cout<<"Case #"<<x<<": "<<y<<'\n';
  15. #define inputstl(v) for(auto& x:v) cin>>x;
  16. #define input(arr,n) for(ull i=0;i<n;++i){cin>>(arr)[i];}
  17. #define print(arr,n) for(ull i=0;i<n;++i){cout<<(arr)[i]<<" ";}cout<<'\n';
  18. #define printall(x) {for(auto y:x){cout<<y<<' ';}cout<<'\n';}
  19. #define printallpii(x) for(auto y:x){cout<<y.fi<<','<<y.se<<' ';}cout<<'\n';
  20. #define print_err(arr,n) for(ull i=0;i<n;++i){cerr<<(arr)[i]<<" ";}cerr<<'\n';
  21. #define printall_err(x) for(auto y:x){cerr<<y<<' ';}cerr<<'\n';
  22. #define printallpii_err(x) for(auto y:x){cerr<<y.fi<<','<<y.se<<' ';}cerr<<'\n';
  23. #define fi first
  24. #define se second
  25. #define pb push_back
  26. #define eb emplace_back
  27. #define mp make_pair
  28. #define mt make_tuple
  29. #define pii pair<int,int>
  30. #define pll pair<long long,long long>
  31. #define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  32. #define SENSITIVITY 1e-9
  33. #define EQUAL(xx1,xx2) [](auto x1,auto x2){double ep=0.0001;double pos=x1-x2;if(pos<0){pos=-pos;}double maxi=(x1>x2)?(x1):(x2);if(pos/(maxi*ep)<SENSITIVITY)return true;else return false;}(xx1,xx2)
  34. #define pack(x) x.begin(),x.end()
  35.  
  36. constexpr int64_t mod=1e9+7;
  37.  
  38. struct timer
  39. {
  40. private:
  41. static int __timer_number;
  42. public:
  43. int timer_number;
  44. chrono::high_resolution_clock::time_point t1;
  45. timer(): t1(chrono::high_resolution_clock::now()),timer_number(__timer_number++)
  46. {
  47. cout<<"timer number "<<timer_number<<" init\n";
  48. }
  49. timer(const timer& t):t1(t.t1),timer_number(__timer_number++)
  50. {
  51. cout<<"timer number "<<timer_number<<" init\n";
  52. }
  53. template<class T=chrono::milliseconds>
  54. auto give_time()
  55. {
  56. chrono::high_resolution_clock::time_point t2;
  57. t2=chrono::high_resolution_clock::now();
  58. return chrono::duration_cast<T>(t2-t1);
  59. }
  60. template<class T=chrono::milliseconds>
  61. void print_time()
  62. {
  63. chrono::high_resolution_clock::time_point t2;
  64. t2=chrono::high_resolution_clock::now();
  65. auto d=chrono::duration_cast<T>(t2-t1);
  66. cout<<"time (default:milli) until now by timer "<<timer_number<<" : "<<d.count()<<'\n';
  67. }
  68. ~timer()
  69. {
  70. __timer_number--;
  71. }
  72. };
  73. int timer::__timer_number=0;
  74.  
  75. // //this does not support . character matching (globbing)
  76. // //to do that add the code from your solution of leetcode 211
  77. // //add a new static element to the node, named defaulter and use that for globbing
  78.  
  79. // template<class T>
  80. // class trie{
  81. // private:
  82. // vector<T> hold;
  83. // int hold_size;
  84. // int found;
  85. // int _size;
  86. // struct node{
  87. // map<T,node*> link;
  88. // int ending;
  89. // node():link(map<T,node*>()),ending(0)
  90. // {
  91.  
  92. // }
  93. // ~node()
  94. // {
  95.  
  96. // }
  97. // };
  98. // node root;
  99. // void __traverse(node* const p,int index)
  100. // {
  101. // if(index==hold_size)
  102. // {
  103. // // if(p->ending>0)
  104. // // found=;
  105. // found=p->ending;
  106. // return ;
  107. // }
  108. // // if(hold[index]=='.')
  109. // // {
  110. // // for(auto& x:p->link)
  111. // // {
  112. // // traverse(x.second,index+1);
  113. // // if(found)
  114. // // return ;
  115. // // }
  116. // // }
  117. // // else
  118. // // {
  119. // auto it=p->link.find(hold[index]);
  120. // if(it!=p->link.end())
  121. // {
  122. // __traverse(it->second,index+1);
  123. // }
  124. // // }
  125. // }
  126. // bool __del_traverse(node* const p,int index)
  127. // {
  128. // if(index==hold_size)
  129. // {
  130. // if(!p->ending)
  131. // {
  132. // --p->ending;
  133. // return 1;
  134. // }
  135. // return 0;
  136. // }
  137. // auto it=p->link.find(hold[index]);
  138. // if(it!=p->link.end())
  139. // {
  140. // return __del_traverse(it->second,index+1);
  141. // }
  142. // return 0;
  143. // }
  144. // void __dfs_clear(node* const p)
  145. // {
  146. // for(auto& x:p->link)
  147. // {
  148. // __dfs_clear(x.second);
  149. // delete x.second;
  150. // }
  151.  
  152. // }
  153. // public:
  154. // trie():_size(0)
  155. // {
  156.  
  157. // }
  158. // void add_stuff(const vector<T>& v)
  159. // {
  160. // hold.assign(v.begin(),v.end());
  161. // hold_size=v.size();
  162. // int index=0;
  163. // node* cur=&root;
  164. // while(index!=hold_size)
  165. // {
  166. // auto it=cur->link.find(hold[index]);
  167. // if(it==cur->link.end())
  168. // {
  169. // // test(1);
  170. // cur->link[hold[index]]=new node();
  171. // // cur=cur->link[hold[index]];
  172. // }
  173. // cur=cur->link[hold[index]];
  174. // ++index;
  175. // }
  176. // ++(cur->ending);
  177. // ++_size;
  178. // }
  179. // int find_stuff(const vector<T>& v)
  180. // {
  181. // found=0;
  182. // hold.assign(v.begin(),v.end());
  183. // hold_size=v.size();
  184. // __traverse(&root,0);
  185. // return found;
  186. // }
  187. // bool delete_stuff(const vector<T>& v)
  188. // {
  189. // hold.assign(v.begin(),v.end());
  190. // hold_size=v.size();
  191. // auto val=__del_traverse(&root,0);
  192. // if(val)
  193. // --_size;
  194. // return val;
  195. // }
  196. // void clear()
  197. // {
  198. // __dfs_clear(&root);
  199. // root.link.clear();
  200. // _size=0;
  201. // }
  202. // int size()
  203. // {
  204. // return _size;
  205. // }
  206. // ~trie()
  207. // {
  208. // clear();
  209. // }
  210. // };
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217. template<class A>
  218. void ____internal__print(string s,A a)
  219. {
  220. auto index=s.find(',');
  221. cerr<<s.substr(0,index)<<": "<<a<<'\n';
  222. }
  223. template<class A,class ... B>
  224. void ____internal__print(string s,A a,B... b)
  225. {
  226. auto index=s.find(',');
  227. cerr<<s.substr(0,index)<<": "<<a<<", ";
  228. ____internal__print(s.substr(index+1,(int)s.length()-index-1),b...);
  229. }
  230.  
  231. #define debug(...) \
  232. {string __debug__s__=string(#__VA_ARGS__)+",";____internal__print(__debug__s__,__VA_ARGS__);}
  233.  
  234. // bool isPrime(ll a)
  235. // {
  236. // if(a==1)
  237. // return false;
  238. // for(ll i=2; i*i<=a; ++i)
  239. // {
  240. // if(a%i==0)
  241. // {
  242. // return false;
  243. // }
  244. // }
  245. // return true;
  246. // }
  247. // bool isPali(string s)
  248. // {
  249. // int _size=(s.length())/2;
  250. // for(int i=0; i<_size; ++i)
  251. // {
  252. // if(s.at(i)!=s.at(s.length()-1-i))
  253. // {
  254. // return false;
  255. // }
  256. // }
  257. // return true;
  258. // }
  259. // int gcd(int a,int b)
  260. // {
  261. // if(a==0)
  262. // {
  263. // return b;
  264. // }
  265. // else if(b==0)
  266. // {
  267. // return a;
  268. // }
  269. // else
  270. // {
  271. // int shift=__builtin_ctz(a|b);
  272. // a>>=__builtin_ctz(a);
  273. // do
  274. // {
  275. // b>>=__builtin_ctz(b);
  276. // if(a>b)
  277. // {
  278. // a=a^b;
  279. // b=a^b;
  280. // a=a^b;
  281. // }
  282. // b-=a;
  283. // }
  284. // while(b);
  285. // return a<<shift;
  286. // }
  287. // }
  288. // ll gcdll(ll a,ll b)
  289. // {
  290. // if(a==0)
  291. // {
  292. // return b;
  293. // }
  294. // else if(b==0)
  295. // {
  296. // return a;
  297. // }
  298. // else
  299. // {
  300. // ll shift=__builtin_ctzll(a|b);
  301. // a>>=__builtin_ctzll(a);
  302. // do
  303. // {
  304. // b>>=__builtin_ctzll(b);
  305. // if(a>b)
  306. // {
  307. // a=a^b;
  308. // b=a^b;
  309. // a=a^b;
  310. // }
  311. // b-=a;
  312. // }
  313. // while(b);
  314. // return a<<shift;
  315. // }
  316. // }
  317. // ll power(ll a,ll b,ll _mod)
  318. // {
  319. // a%=_mod;
  320. // ll temp=a;
  321. // ll ans=1;
  322. // if(!b)
  323. // return 1;
  324. // int limit=63-__builtin_clzll(b);
  325. // int index=0;
  326. // while(index<=limit)
  327. // {
  328. // if(b&(1ll<<index))
  329. // {
  330. // ans=(ans*temp)%_mod;
  331. // }
  332. // ++index;
  333. // temp=(temp*temp)%_mod;
  334. // }
  335. // return ans;
  336. // }
  337. // template<class T>
  338. // inline void swapper(const T& d1,const T& d2)
  339. // {
  340. // for(int i=0;i<sizeof(T);++i)
  341. // {
  342. // *((char*)(&d1)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  343. // }
  344. // for(int i=0;i<sizeof(T);++i)
  345. // {
  346. // *((char*)(&d2)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  347. // }
  348. // for(int i=0;i<sizeof(T);++i)
  349. // {
  350. // *((char*)(&d1)+i)=(*((char*)(&d1)+i))^(*((char*)(&d2)+i));
  351. // }
  352. // }
  353.  
  354. // int kmp(const string& s,const string& t)
  355. // {
  356. // int s_size=s.size(),t_size=t.size();
  357. // if(s_size<t_size)
  358. // return 0;
  359. // vector<int> arr(t_size);
  360. // int len=0;
  361. // for(int i=0;i<t_size;++i)
  362. // {
  363. // if(!i)
  364. // {
  365. // arr[i]=0;
  366. // continue;
  367. // }
  368. // while(1)
  369. // {
  370. // if(t[len]==t[i])
  371. // {
  372. // arr[i]=++len;
  373. // break;
  374. // }
  375. // if(!len)
  376. // {
  377. // arr[i]=0;
  378. // break;
  379. // }
  380. // len=arr[len-1];
  381. // }
  382. // }
  383. // //printall(arr);
  384. // int ans=0;
  385. // for(int j=0,i=0;i<s_size;++i,++j)
  386. // {
  387. // // debug(i,j);
  388. // if(s[i]==t[j])
  389. // {
  390. // if(j==t.length()-1)
  391. // {
  392. // //debug(i,j)
  393. // j=arr[j]-1;
  394. // //debug(j);
  395. // ++ans;
  396. // }
  397. // continue;
  398. // }
  399. // if(!j)
  400. // {
  401. // --j;
  402. // continue;
  403. // }
  404. // --i;
  405. // j=arr[j-1]-1;
  406. // }
  407. // return ans;
  408. // }
  409. // template<class T>
  410. // vector<T> LIS(vector<T> a)
  411. // {
  412. // int n=a.size();
  413. // vector<pair<T,int>> v;
  414. // vector<T*> add(n);
  415. // add[0]=nullptr;
  416. // v.push_back(make_pair(a[0],0));
  417. // auto f=[](pair<T,int> a,pair<T,int> b){return a.first<b.first;};
  418. // for(int i=1;i<n;++i)
  419. // {
  420. // auto it=lower_bound(v.begin(),v.end(),make_pair(a[i],-1),f);
  421. // if(it==v.end())
  422. // {
  423. // add[i]=&a[0]+v.back().second;
  424. // v.push_back(make_pair(a[i],i));
  425. // }
  426. // else
  427. // {
  428. // it->first=a[i];
  429. // it->second=i;
  430. // if(it==v.begin())
  431. // {
  432. // add[i]=nullptr;
  433. // }
  434. // else
  435. // {
  436. // add[i]=&a[0]+(it-1)->second;
  437. // }
  438. // }
  439. // }
  440. // vector<T> ans;
  441. // ans.reserve(v.size());
  442. // T* p=&a[0]+v.back().second;
  443. // while(p!=nullptr)
  444. // {
  445. // ans.push_back(*p);
  446. // p=(add[p-&a[0]]);
  447. // }
  448. // reverse(ans.begin(),ans.end());
  449. // return ans;
  450. // }
  451.  
  452. // ///O(N*N) NOT MANCHAR . BULLSHIT DP
  453. // string longest_palindromic_substring(const string& s)
  454. // {
  455. // if(s.size()<=1)
  456. // return s;
  457. // int len=s.size();
  458. // vector<bool> odd(s.size(),1);
  459. // vector<bool> even(s.size(),0);
  460. // string ans=string(1,s[0]);
  461. // for(int i=0;i<len-1;++i)
  462. // {
  463. // if(s[i]==s[i+1])
  464. // {
  465. // even[i]=1;
  466. // if(ans.size()<2)
  467. // ans=s.substr(i,2);
  468. // }
  469. // }
  470. // for(int i=3;i<=len;++i)
  471. // {
  472. // if(i&1)
  473. // {
  474. // for(int j=0;j<=len-i;++j)
  475. // {
  476. // odd[j]=(s[j]==s[j+i-1])&&(odd[j+1]);
  477. // if(odd[j]&&ans.size()<i)
  478. // ans=s.substr(j,i);
  479. // }
  480. // }
  481. // else
  482. // {
  483. // for(int j=0;j<=len-i;++j)
  484. // {
  485. // even[j]=(s[j]==s[j+i-1])&&(even[j+1]);
  486. // if(even[j]&&ans.size()<i)
  487. // ans=s.substr(j,i);
  488. // }
  489. // }
  490. // }
  491. // return ans;
  492. // }
  493.  
  494.  
  495. // template<class S>
  496. // S longestSubarraySum(auto start,auto end)
  497. // {
  498. // S val=0;
  499. // S maxi=*start;
  500. // for(auto s=start;s!=end;++s)
  501. // {
  502. // if(val+*s>=*s)
  503. // {
  504. // val+=*s;
  505. // }
  506. // else
  507. // {
  508. // val=*s;
  509. // }
  510. // if(maxi<val)
  511. // {
  512. // maxi=val;
  513. // }
  514. // }
  515. // return maxi;
  516. // }
  517.  
  518. // template<class T>
  519. // T fibo(T x,T _mod)
  520. // {
  521. // if(x==1)
  522. // {
  523. // return (T)0;
  524. // }
  525. // else if(x==2)
  526. // {
  527. // return (T)1;
  528. // }
  529. // // x*=2;// made it twice to get the actual value
  530. // stack<pair<T,T>> st;
  531. // while(x>1)
  532. // {
  533. // st.push(make_pair(x,x+1));
  534. // x/=2;
  535. // }
  536. // //start with an even means the same components
  537. // //otherwise component change
  538. // T a=0;
  539. // T b=1;
  540. // T c;
  541. // while(st.size())
  542. // {
  543. // auto p=st.top();
  544. // st.pop();
  545. // T cur_a;
  546. // T cur_b;
  547. // if(p.first&1)
  548. // {
  549. // cur_a=(b*b+2*a*b)%_mod;
  550. // b=(a+b)%_mod;
  551. // a=(b-a+_mod)%_mod;
  552. // cur_b=(a*a+b*b)%_mod;
  553. // }
  554. // else
  555. // {
  556. // cur_a=(a*a+b*b)%_mod;
  557. // cur_b=(b*b+2*a*b)%_mod;
  558. // }
  559. // a=cur_a;
  560. // b=cur_b;
  561. // }
  562. // return a;
  563. // }
  564.  
  565. // // #pragma GCC optimize("Ofast")
  566. // // #pragma GCC optimize("unroll-loops")
  567.  
  568.  
  569. // int main()
  570. // {
  571. // // #ifdef ONLINE_JUDGE
  572. // // #include <sys/resource.h>
  573. // // rlimit R;
  574. // // getrlimit(RLIMIT_STACK, &R);
  575. // // R.rlim_cur = R.rlim_max;
  576. // // setrlimit(RLIMIT_STACK, &R);
  577. // // #endif
  578. // //define cin fin
  579. // //ifstream fin;
  580. // //fin.open("input.txt",ios_base::in);
  581.  
  582. // // fastio;
  583. // // freopen("input.txt","r",stdin);
  584. // //freopen("output.txt","w",stdout);
  585. // int tt=1;
  586. // // cin>>tt;
  587. // // scanf("%d",&tt);
  588. // // timer t;
  589. // int ittt=1;
  590. // //////CHECK FOR EDGE CASES DUMMY!!!!!!!!!!!/////
  591. // while(tt--)
  592. // {
  593. // vector<vector<int>> v;
  594. // int s,t;
  595. // int n,m;
  596. // int visited[(int)1e5+10][3]={};
  597. // int ans=-1;
  598.  
  599. // cin>>n>>m;
  600. // v.assign(n+1,vector<int>());
  601. // for(int i=0;i<m;++i)
  602. // {
  603. // int x,y;
  604. // cin>>x>>y;
  605. // v[x].push_back(y);
  606. // }
  607. // cin>>s>>t;
  608. // {
  609. // visited[s][0]=1;
  610. // queue<pair<int,int>> q;
  611. // q.push(make_pair(s,0));
  612. // while(q.size())
  613. // {
  614. // auto p=q.front();
  615. // q.pop();
  616. // if(p.first==t && p.second%3==0)
  617. // {
  618. // ans=p.second;
  619. // break;
  620. // }
  621. // for(auto& t:v[p.first])
  622. // {
  623. // if(visited[t][(p.second+1)%3])
  624. // continue;
  625. // visited[t][(p.second+1)%3]=1;
  626. // q.push(make_pair(t,p.second+1));
  627. // }
  628. // }
  629. // }
  630. // if(ans==-1)
  631. // cout<<ans<<"\n";
  632. // else
  633. // cout<<ans/3<<"\n";
  634.  
  635. // }
  636. // // t.print_time();
  637. // return 0;
  638. // }
  639.  
  640.  
  641.  
  642.  
  643. // Program to show segment tree to demonstrate laz
  644. #define MAX 400100
  645.  
  646. // Ideally, we should not use global variables and large
  647. // constant-sized arrays, we have done it here for simplicity.
  648. int tree[MAX] = {0}; // To store segment tree
  649. int lazy[MAX] = {0}; // To store pending updates
  650.  
  651. /* si -> index of current node in segment tree
  652. ss and se -> Starting and ending indexes of elements for
  653. which current nodes stores sum.
  654. us and ue -> starting and ending indexes of update query
  655. diff -> which we need to add in the range us to ue */
  656. void updateRangeUtil(int si, int ss, int se, int us,
  657. int ue, int diff)
  658. {
  659. // If lazy value is non-zero for current node of segment
  660. // tree, then there are some pending updates. So we need
  661. // to make sure that the pending updates are done before
  662. // making new updates. Because this value may be used by
  663. // parent after recursive calls (See last line of this
  664. // function)
  665. if (lazy[si] != 0)
  666. {
  667. // Make pending updates using value stored in lazy
  668. // nodes
  669. tree[si] += (se-ss+1)*lazy[si];
  670.  
  671. // checking if it is not leaf node because if
  672. // it is leaf node then we cannot go further
  673. if (ss != se)
  674. {
  675. // We can postpone updating children we don't
  676. // need their new values now.
  677. // Since we are not yet updating children of si,
  678. // we need to set lazy flags for the children
  679. lazy[si*2 + 1] += lazy[si];
  680. lazy[si*2 + 2] += lazy[si];
  681. }
  682.  
  683. // Set the lazy value for current node as 0 as it
  684. // has been updated
  685. lazy[si] = 0;
  686. }
  687.  
  688. // out of range
  689. if (ss>se || ss>ue || se<us)
  690. return ;
  691.  
  692. // Current segment is fully in range
  693. if (ss>=us && se<=ue)
  694. {
  695. // Add the difference to current node
  696. tree[si] += (se-ss+1)*diff;
  697.  
  698. // same logic for checking leaf node or not
  699. if (ss != se)
  700. {
  701. // This is where we store values in lazy nodes,
  702. // rather than updating the segment tree itelf
  703. // Since we don't need these updated values now
  704. // we postpone updates by storing values in lazy[]
  705. lazy[si*2 + 1] += diff;
  706. lazy[si*2 + 2] += diff;
  707. }
  708. return;
  709. }
  710.  
  711. // If not completely in rang, but overlaps, recur for
  712. // children,
  713. int mid = (ss+se)/2;
  714. updateRangeUtil(si*2+1, ss, mid, us, ue, diff);
  715. updateRangeUtil(si*2+2, mid+1, se, us, ue, diff);
  716.  
  717. // And use the result of children calls to update this
  718. // node
  719. tree[si] = tree[si*2+1] ^ tree[si*2+2];
  720. }
  721.  
  722. // Function to update a range of values in segment
  723. // tree
  724. /* us and eu -> starting and ending indexes of update query
  725. ue -> ending index of update query
  726. diff -> which we need to add in the range us to ue */
  727. void updateRange(int n, int us, int ue, int diff)
  728. {
  729. updateRangeUtil(0, 0, n-1, us, ue, diff);
  730. }
  731.  
  732.  
  733. /* A recursive function to get the sum of values in given
  734. range of the array. The following are parameters for
  735. this function.
  736. si --> Index of current node in the segment tree.
  737. Initially 0 is passed as root is always at'
  738. index 0
  739. ss & se --> Starting and ending indexes of the
  740. segment represented by current node,
  741. i.e., tree[si]
  742. qs & qe --> Starting and ending indexes of query
  743. range */
  744. int getSumUtil(int ss, int se, int qs, int qe, int si)
  745. {
  746. // If lazy flag is set for current node of segment tree,
  747. // then there are some pending updates. So we need to
  748. // make sure that the pending updates are done before
  749. // processing the sub sum query
  750. if (lazy[si] != 0)
  751. {
  752. // Make pending updates to this node. Note that this
  753. // node represents sum of elements in arr[ss..se] and
  754. // all these elements must be increased by lazy[si]
  755. tree[si] += (se-ss+1)*lazy[si];
  756.  
  757. // checking if it is not leaf node because if
  758. // it is leaf node then we cannot go further
  759. if (ss != se)
  760. {
  761. // Since we are not yet updating children os si,
  762. // we need to set lazy values for the children
  763. lazy[si*2+1] += lazy[si];
  764. lazy[si*2+2] += lazy[si];
  765. }
  766.  
  767. // unset the lazy value for current node as it has
  768. // been updated
  769. lazy[si] = 0;
  770. }
  771.  
  772. // Out of range
  773. if (ss>se || ss>qe || se<qs)
  774. return 0;
  775.  
  776. // At this point we are sure that pending lazy updates
  777. // are done for current node. So we can return value
  778. // (same as it was for query in our previous post)
  779.  
  780. // If this segment lies in range
  781. if (ss>=qs && se<=qe)
  782. return tree[si];
  783.  
  784. // If a part of this segment overlaps with the given
  785. // range
  786. int mid = (ss + se)/2;
  787. return getSumUtil(ss, mid, qs, qe, 2*si+1) ^
  788. getSumUtil(mid+1, se, qs, qe, 2*si+2);
  789. }
  790.  
  791. // Return sum of elements in range from index qs (query
  792. // start) to qe (query end). It mainly uses getSumUtil()
  793. int getSum(int n, int qs, int qe)
  794. {
  795. // Check for erroneous input values
  796. if (qs < 0 || qe > n-1 || qs > qe)
  797. {
  798. // printf("Invalid Input");
  799. return -1;
  800. }
  801.  
  802. return getSumUtil(0, n-1, qs, qe, 0);
  803. }
  804.  
  805. // A recursive function that constructs Segment Tree for
  806. // array[ss..se]. si is index of current node in segment
  807. // tree st.
  808. void constructSTUtil(int arr[], int ss, int se, int si)
  809. {
  810. // out of range as ss can never be greater than se
  811. if (ss > se)
  812. return ;
  813.  
  814. // If there is one element in array, store it in
  815. // current node of segment tree and return
  816. if (ss == se)
  817. {
  818. tree[si] = arr[ss];
  819. return;
  820. }
  821.  
  822. // If there are more than one elements, then recur
  823. // for left and right subtrees and store the sum
  824. // of values in this node
  825. int mid = (ss + se)/2;
  826. constructSTUtil(arr, ss, mid, si*2+1);
  827. constructSTUtil(arr, mid+1, se, si*2+2);
  828.  
  829. tree[si] = tree[si*2 + 1] ^ tree[si*2 + 2];
  830. }
  831.  
  832. /* Function to construct segment tree from given array.
  833. This function allocates memory for segment tree and
  834. calls constructSTUtil() to fill the allocated memory */
  835. void constructST(int arr[], int n)
  836. {
  837. // Fill the allocated memory st
  838. constructSTUtil(arr, 0, n-1, 0);
  839. }
  840. int findXOR(int n)
  841. {
  842. int mod = n % 4;
  843.  
  844. // If n is a multiple of 4
  845. if (mod == 0)
  846. return n;
  847.  
  848. // If n % 4 gives remainder 1
  849. else if (mod == 1)
  850. return 1;
  851.  
  852. // If n % 4 gives remainder 2
  853. else if (mod == 2)
  854. return n + 1;
  855.  
  856. // If n % 4 gives remainder 3
  857. else if (mod == 3)
  858. return 0;
  859. return 1;
  860. }
  861.  
  862. // Function to return the XOR of elements
  863. // from the range [l, r]
  864. int findXOR(int l, int r)
  865. {
  866. return (findXOR(l - 1) ^ findXOR(r));
  867. }
  868.  
  869. // Driver program to test above functions
  870. int main()
  871. {
  872. int n,q;
  873. cin>>n>>q;
  874. int* arr=new int[n+10];
  875. for(int i=0;i<n+10;++i)
  876. {
  877. arr[i]=1;
  878. }
  879. // int* arr[] = {1, 3, 5, 7, 9, 11};
  880.  
  881. // Build segment tree from given array
  882. constructST(arr, n);
  883. for(int i=0;i<q;++i)
  884. {
  885. for(int i=0;i<n;++i)
  886. {
  887. cout<<getSum(n,i,i)<<" ";
  888. }
  889. cout<<"\n";
  890. // debug(i);
  891. int a1,a2,a3,a4;
  892. cin>>a1>>a2>>a3>>a4;
  893. int val1=findXOR(a1,a2);//correct xor//0 based answer
  894. int val2=findXOR(a3,a4);//correct xor
  895. if(val1>val2)
  896. swap(val1,val2);
  897. int xo=a1^a2^a3^a4;
  898. // debug(xo);
  899. updateRange(n,val1,val2,xo);
  900. }
  901. // // Print sum of values in array from index 1 to 3
  902. // // printf("Sum of values in given range = %d\n",
  903. // getSum(n, 1, 3));
  904.  
  905. // // Add 10 to all nodes at indexes from 1 to 5.
  906. // updateRange(n, 1, 5, 10);
  907.  
  908. // // Find sum after the value is updated
  909. // // printf("Updated sum of values in given range = %d\n",
  910. // getSum( n, 1, 3));
  911. for(int i=0;i<n;++i)
  912. {
  913. cout<<getSum(n,i,i)<<" ";
  914. }
  915. cout<<"\n";
  916. return 0;
  917. }
  918.  
Add Comment
Please, Sign In to add comment
Public Pastes
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.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!