#include using namespace std; #define REP(i,a,b) for(i=a;i*r =(pair*)mem; rep(i,n1) r[i].first = arr1[i],r[i].second = i; rep(i,n2) r[n1+i].first = arr2[i],r[n1+i].second = n1+i; sort(r, r+n1+n2); rep(i,n1+n2){ if(i&&r[i].first!=r[i-1].first) k++; if(r[i].second= 0 && A[bf[i]] <= A[i]) bf[i] = bf[bf[i]]; } // bf[i] denotes the index j of the rightmost elements of j < i && A[j] > A[i], it will be done in O(N) time:) nx[N-1] = N; for(i=N-2;i>=0;i--){ nx[i] = i+1; while(nx[i] < N && A[nx[i]] < A[i]) nx[i] = nx[nx[i]]; } // nx[i] denotes the index j of the leftmost elements of j > i && A[j] >= A[i] c = coordinateCompress(N, A, M, K, mem); // if A={100,400,500}, K={370,900,400,400} then this function make A={0,2,3}, K={1,4,2,2} and return 5 (number of distinct values) rep(i,N) val[A[i]] ^= ( (i-bf[i])&1 ) & ( (nx[i]-i)&1 ); rep(i,c) sum[i+1] = sum[i] ^ val[i]; rep(i,M){ if(X[i]=='<'){ k = sum[K[i]]; } else if(X[i]=='='){ k = val[K[i]]; } else { k = sum[c] ^ sum[K[i]+1]; } if(C[i]=='D') k ^= 1; putchar(k?'C':'D'); } puts(""); return 0; }