Untitled
unknown
c_cpp
2 years ago
2.4 kB
14
Indexable
#include <iostream> #include <algorithm> using namespace std; struct node{ int mini; int maxi; }; int n; node tree[400003]; int arr[100001]; void init(int node, int start, int end){ if(start==end){ tree[node].maxi = arr[start]; tree[node].mini = arr[start]; return; } int mid = (start+end)>>1; init(2*node, start, mid); init(2*node+1, mid+1, end); tree[node].mini = min(tree[2*node].mini, tree[2*node+1].mini); tree[node].maxi = max(tree[2*node].maxi, tree[2*node+1].maxi); return; } void update(int node, int start, int end, int idx, int change){ if(idx < start || idx > end){ return; } if(start == end){ tree[node] = {change, change}; // arr[idx] = change; return; } int mid = (start+end)>>1; update(2*node, start, mid, idx, change); update(2*node+1, mid+1, end, idx, change); tree[node] = {min(tree[2*node].mini, tree[2*node+1].mini), max(tree[2*node].maxi, tree[2*node+1].maxi)}; } // node left, node right node query(int N, int start, int end, int left, int right){ if(start > right || end < left){ // default return {INT32_MAX, INT32_MIN}; } if(left<= start && end <= right){ return tree[N]; } int mid = (start+end)>>1; node L = query(2*N, start, mid, left, right); node R = query(2*N+1, mid+1, end, left, right); return {min(L.mini, R.mini), max(L.maxi, R.maxi)}; } int main(void){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int t; cin >> t; while(t--){ int k; cin >> n >> k; for(int i = 0;i<4*n;i++){ tree[i] = {INT32_MAX, -1}; } for(int i = 1;i<=n;i++){ arr[i] = i; } init(1,0,n-1); int q, a, b; while(k--){ cin >> q; if(q==0){ cin >> a >> b; // A <- B int A = arr[a]; // B <- A int B = arr[b]; update(1,0,n-1,b,A); update(1,0,n-1,a,B); swap(arr[a], arr[b]); }else{ cin >> a >> b; node res = query(1,0,n-1,a,b); if(res.mini == a && res.maxi == b){ cout << "YES\n"; }else{ cout << "NO\n"; } } } } }
Editor is loading...