#include #define rep(i,x,y) for (int i = (x); i<=(y); i++) #define repe(i,x,y) for (int i = (x); i < (y);i++) #define drep(i,x,y) for (int i = (x); i >= (y); i--) #define mp make_pair #define pb push_back #define MAX(a,b) (((a)>(b))?(a):(b)) #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAXN 60000 #define sf(n) scanf("%Lf",&n) #define prf(n) printf("%Lf",n) #define s(n) scanf("%d",&n) #define sl(n) scanf("%lld",&n) #define pr(n) printf("%d",n) #define prl(n) printf("%lld",n) #define endc printf("\n") #define psp printf(" ") using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; typedef struct report { int many, color; bool all; } report; report newreport(int many,int color,bool all) { report x = *new report(); x.many = many; x.color = color; x.all = all; return x; } int n,m; int lft[8*MAXN]; int ln[8*MAXN]; int rn[8*MAXN]; int rgt[8*MAXN]; int sz[8*MAXN]; bool lazy[8*MAXN]; bool entire(int x) { if (rgt[x] == sz[x]) return true; return false; } void dev(int x) { lft[x] = lft[x*2]; ln[x] = ln[x*2]; if (entire(x*2) && ln[x*2] == ln[x*2 + 1]) { lft[x] += lft[x*2 + 1]; } rgt[x] = rgt[x*2 + 1]; rn[x] = rn[x*2 + 1]; if (entire(x*2 +1) && rn[x*2] == rn[x*2 + 1]) { rgt[x] += rgt[x*2]; } } void push(int x) { // means x is monochrome if (!lazy[x]) return; assert(entire(x)); lazy[x*2] = true; lazy[x*2 + 1] = true; lazy[x] = false; int color = ln[x]; ln[x*2] = rn[x*2] = ln[x*2 + 1] = rn[x*2 + 1] = color; lft[x*2] = rgt[x*2] = sz[x*2]; lft[x*2 + 1] = rgt[x*2 + 1] = sz[x*2 + 1]; } void init(int x,int l,int r) { lazy[x] = false; sz[x] = r-l+1; if (l == r) { lft[x] = 1; rgt[x] = 1; ln[x] = 0; rn[x] = 0; return; } int mid = (l+r)/2; init(x*2,l,mid); init(x*2 + 1,mid+1,r); dev(x); } void update(int x,int l,int r,int i,int j,int c) { push(x); if (j < l || r < i) return; if (i <= l && r <= j) { ln[x] = rn[x] = c; lft[x] = rgt[x] = sz[x]; lazy[x] = true; return; } int mid = (l+r)/2; update(x*2,l,mid,i,j,c); update(x*2 + 1,mid+1,r,i,j,c); dev(x); //cout< mid) { return rightquery(x*2 + 1,mid+1,r,p); } else { report ans = rightquery(x*2,l,mid,p); //cout<<" : "<