fork(1) download
  1. //teja349
  2. #include <bits/stdc++.h>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <climits>
  10. #include <utility>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <queue>
  14. #include <stack>
  15. #include <iomanip>
  16. //setbase - cout << setbase (16); cout << 100 << endl; Prints 64
  17. //setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
  18. //setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
  19. //cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
  20.  
  21. using namespace std;
  22. #define f(i,a,b) for(i=a;i<b;i++)
  23. #define rep(i,n) f(i,0,n)
  24. #define fd(i,a,b) for(i=a;i>=b;i--)
  25. #define pb push_back
  26. #define mp make_pair
  27. #define vi vector< int >
  28. #define vl vector< ll >
  29. #define ss second
  30. #define ff first
  31. #define ll long long
  32. #define pii pair< int,int >
  33. #define pll pair< ll,ll >
  34. #define sz(a) a.size()
  35. #define inf (1000*1000*1000+5)
  36. #define all(a) a.begin(),a.end()
  37. #define tri pair<int,pii>
  38. #define vii vector<pii>
  39. #define vll vector<pll>
  40. #define viii vector<tri>
  41. #define mod (1000*1000*1000+7)
  42. #define pqueue priority_queue< int >
  43. #define pdqueue priority_queue< int,vi ,greater< int > >
  44. #define flush fflush(stdout)
  45. #define primeDEN 727999983
  46. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  47.  
  48. template <typename T>
  49. void printvec(vector<T>& vec){
  50. for(int i=0;i<vec.size();i++){
  51. cout<<vec[i]<<" ";
  52. }
  53. cout<<endl;
  54. }
  55. int ans = 0;
  56. vector<vi> vec(123456);
  57. map<int,int> mapi;
  58. int adder(int st,int en,int elem){
  59. if(mapi.find(elem)==mapi.end())
  60. return 0;
  61. elem=mapi[elem];
  62. int haha=upper_bound(all(vec[elem]),en)-lower_bound(all(vec[elem]),st);
  63. ans+=haha;
  64. return 0;
  65. }
  66. int remov(int st,int en,int elem){
  67. if(mapi.find(elem)==mapi.end())
  68. return 0;
  69. elem=mapi[elem];
  70. int haha=upper_bound(all(vec[elem]),en)-lower_bound(all(vec[elem]),st);
  71. ans-=haha;
  72. return 0;
  73. }
  74. int a[123456],b[123456];
  75. int main(){
  76. //std::ios::sync_with_stdio(false); cin.tie(NULL);
  77. int t;
  78. cin>>t;
  79. // assert(t==5);
  80. while(t--){
  81. int n,q;
  82. //cin>>n>>q;
  83. scanf("%d",&n);
  84. scanf("%d",&q);
  85. //assert(n==100000);
  86. //assert(q==n);
  87. int i;
  88. set<pii> seti;
  89. rep(i,n){
  90. //cin>>a[i];
  91. scanf("%d",a+i);
  92. //assert(1<=a[i] && a[i]<=1e9);
  93. seti.insert(mp(i,a[i]));
  94. }
  95. seti.insert(mp(n,2));
  96. mapi.clear();
  97. int counter=0;
  98. ans=0;
  99. rep(i,n){
  100. //cin>>b[i];
  101. scanf("%d",b+i);
  102. //assert(1<=b[i] && b[i]<=1e9);
  103. if(b[i]==a[i])
  104. ans++;
  105. if(mapi.find(b[i])==mapi.end())
  106. mapi[b[i]]=counter++;
  107. vec[mapi[b[i]]].pb(i);
  108. }
  109. int l,r,c;
  110. set<pii>::iterator it,it1;
  111. int st,en;
  112. pii papa;
  113. rep(i,q){
  114. //cin>>l>>r>>c;
  115. scanf("%d",&l);
  116. scanf("%d",&r);
  117. scanf("%d",&c);
  118. // int lol;
  119. //cin>>lol;
  120. l^=ans;
  121. r^=ans;
  122. c^=ans;
  123. //assert(1<=l && l<=n);
  124. //assert(l<=r && r<=n);
  125. //assert(1<=c && c<=1e9);
  126. l--;
  127. r--;
  128. it=seti.lower_bound(mp(l,0));
  129. if(it==seti.end() || it->ff!=l){
  130. it--;
  131. papa=*it;
  132. papa.ff=l;
  133. seti.insert(papa);
  134. }
  135. it=seti.lower_bound(mp(r+1,0));
  136. if(it==seti.end() || it->ff!=r+1){
  137. it--;
  138. papa=*it;
  139. papa.ff=r+1;
  140. seti.insert(papa);
  141. }
  142. while(1){
  143. it=seti.lower_bound(mp(l,0));
  144. if(it->ff==r+1)
  145. break;
  146. it1=it;
  147. it1++;
  148. st=it->ff;
  149. en=it1->ff-1;
  150. remov(st,en,it->ss);
  151. seti.erase(it);
  152. }
  153. adder(l,r,c);
  154. seti.insert(mp(l,c));
  155. printf("%d\n",ans);
  156. //cout<<ans<<endl;
  157. // assert(ans==lol);
  158. }
  159. rep(i,counter){
  160. vec[i].clear();
  161. }
  162. }
  163. return 0;
  164. }
Success #stdin #stdout 0s 16208KB
stdin
1
4 3
1 2 3 4
1 1 3 5
0 1 0
0 5 3
1 4 1
stdout
1
0
2