fork(1) download
copy 
  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
comments (?)
stdin
copy 
1
4 3
1 2 3 4
1 1 3 5
0 1 0
0 5 3
1 4 1
stdout
copy 
1
0
2
https://ideone.com/mZoae0
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!