fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 3e5 + 5;
  38. int n, a[N], pos[N], num[N];
  39. ii node[N << 2];
  40.  
  41. void update(int pos, int val) {
  42.     int id = 1, l = 1, r = 3 * n;
  43.     while(l < r) {
  44.         int mid = (l + r) >> 1;
  45.         if (pos > mid) id = (id << 1 | 1), l = mid + 1;
  46.         else id = (id << 1), r = mid;
  47.     }
  48.     node[id] = mp(val, val);
  49.     while(id) {
  50.         id >>= 1;
  51.         node[id].fi = min(node[id << 1].fi, node[id << 1 | 1].fi);
  52.         node[id].se = max(node[id << 1].se, node[id << 1 | 1].se);
  53.     }
  54. }
  55.  
  56. ii get(int id, int l, int r, int u, int v) {
  57.     if (l > v || r < u) return mp(inf, -inf);
  58.     if (u <= l && r <= v) return node[id];
  59.     int mid = (l + r) >> 1;
  60.     ii L = get(id << 1, l, mid, u, v);
  61.     ii R = get(id << 1 | 1, mid + 1, r, u, v);
  62.     return mp(min(L.fi, R.fi), max(L.se, R.se));
  63. }
  64.  
  65. int q;
  66. void init(void) {
  67.     cin >> n;
  68.     FOR(i, 1, 3 * n) {
  69.         cin >> a[i];
  70.         num[i] = a[i];
  71.         pos[a[i]] = i;
  72.         update(i, a[i]);
  73.     }
  74.     cin >> q;
  75. }
  76.  
  77. void process(void) {
  78.     while(q--) {
  79.         char S; cin >> S;
  80.         int a, b; cin >> a >> b;
  81.         if (S == 'S') {
  82.             int pa = pos[a];
  83.             int pb = pos[b];
  84.             num[pa] = b;
  85.             num[pb] = a;
  86.             swap(pos[a], pos[b]);
  87.             update(pos[a], a);
  88.             update(pos[b], b);
  89.         } else {
  90.             int x = num[n];
  91.             if (a <= x && x <= b) {
  92.                 x = n;
  93.                 int low = 1, high = x, res = x;
  94.                 while(low <= high) {
  95.                     int mid = (low + high) >> 1;
  96.                     ii tmp = get(1, 1, 3 * n, mid, x);
  97.                     if (a <= tmp.fi && tmp.se <= b) res = mid, high = mid - 1;
  98.                     else low = mid + 1;
  99.                 }
  100.                 int cnt = x - res + 1;
  101.  
  102.                 low = x, high = 3 * n, res = x;
  103.                 while(low <= high) {
  104.                     int mid = (low + high) >> 1;
  105.                     ii tmp = get(1, 1, 3*n, x, mid);
  106.                     if (a <= tmp.fi && tmp.se <= b) res = mid, low = mid + 1;
  107.                     else high = mid - 1;
  108.                 }
  109.  
  110.                 cnt += res - x;
  111.  
  112.                 if (res < 3 * n) {
  113.                     low = 1, high = 3 * n, res = 3*n+1;
  114.                     while(low <= high) {
  115.                         int mid = (low + high) >> 1;
  116.                         ii tmp = get(1, 1, 3*n, mid, 3 * n);
  117.                         if (a <= tmp.fi && tmp.se <= b) res = mid, high = mid - 1;
  118.                         else low = mid + 1;
  119.                     }
  120.                     cnt += 3*n - res + 1;
  121.                 }
  122.                 cout << (cnt == b-a+1 ? "C" : "U");
  123.  
  124.             } else {
  125.                 x = pos[a];
  126.                 int low = 1, high = x, res = x;
  127.                 while(low <= high) {
  128.                     int mid = (low + high) >> 1;
  129.                     ii tmp = get(1, 1, 3 * n, mid, x);
  130.                     if (a <= tmp.fi && tmp.se <= b) res = mid, high = mid - 1;
  131.                     else low = mid + 1;
  132.                 }
  133.  
  134.                 int cnt = x - res + 1;
  135.  
  136.                 low = x, high = 3 * n, res = x;
  137.                 while(low <= high) {
  138.                     int mid = (low + high) >> 1;
  139.                     ii tmp = get(1, 1, 3*n, x, mid);
  140.                     if (a <= tmp.fi && tmp.se <= b) res = mid, low = mid + 1;
  141.                     else high = mid - 1;
  142.                 }
  143.                 cnt += res - x;
  144.  
  145.                 cout << (cnt == b - a + 1 ? "C" : "U");
  146.             }
  147.         }
  148.     }
  149.     cout << '\n';
  150. }
  151.  
  152. int main() {
  153.     ios_base::sync_with_stdio(0);
  154.     cin.tie(0); cout.tie(0);
  155.     if (fopen(task".inp", "r")) {
  156.         freopen(task".inp", "r", stdin);
  157.         freopen(task".out", "w", stdout);
  158.     }
  159.     int tc = 1;
  160.     cin >> tc;
  161.     while(tc--) {
  162.         init();
  163.         process();
  164.     }
  165.     return 0;
  166. }
  167.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/6ONW3h
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
1 day 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!