| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1097694 | vjudge1 | Inside information (BOI21_servers) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int ll
#define lc (c[rt].l)
#define rc (c[rt].r)
#define mid (l+r>>1)
#define rg register
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define prq priority_queue
#define fi first
#define se second
#define DEBUG printf("Debug on line %d\n", __LINE__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
inline int read(){
int n=0, f=1; char ch = getchar();
for(; !isdigit(ch); ch=getchar()) if(ch == '-') f=-1;
for(; isdigit(ch); ch=getchar()) n=n*10+ch-'0';
return n*f;
}
int n, q;
int rt[N];
char opt[N]; int a[N], b[N], ans[N];
namespace dgb_SEG{
int tp = 0;
struct node{
int s;
int l, r;
}c[N*400];
void clear(){
for(int i=1; i<=tp; i++){
c[i].l = c[i].r = c[i].s = 0;
}
tp = 0;
}
int newnode(){
++tp;
c[tp].l = c[tp].r = c[tp].s = 0;
return tp;
}
int clone(int x){
c[++tp] = c[x];
return tp;
}
void pushup(int rt){
c[rt].s = c[lc].s + c[rc].s;
}
int merge(int x, int y, int l, int r){
if(!x || !y) return x|y;
int rt = newnode();
if(l == r){
c[rt].s = c[x].s + c[y].s;
return rt;
}
lc = merge(c[x].l, c[y].l, l, mid);
rc = merge(c[x].r, c[y].r, mid+1, r);
pushup(rt);
return rt;
}
int modify(int rt, int l, int r, int x, int v){
rt = clone(rt);
if(l == r){
c[rt].s += v;
return rt;
}
if(x <= mid) lc = modify(lc, l, mid, x, v);
else rc = modify(rc, mid+1, r, x, v);
pushup(rt);
return rt;
}
int multiQuery(int rt, int l, int r, int ql, int qr){
if(!rt || ql>qr || l>qr || r<ql) return 0;
if(l>=ql && r<=qr) return c[rt].s;
return multiQuery(lc, l, mid, ql, qr) + multiQuery(rc, mid+1, r, ql, qr);
}
int singleQuery(int rt, int l, int r, int x){
if(l == r) return c[rt].s;
if(x <= mid) return singleQuery(lc, l, mid, x);
else return singleQuery(rc, mid+1, r, x);
}
}
/*
6 4
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
*/
signed main(){
// printf("%lld\n", N);
n = read(), q = read();
q += n-1;
for(int i=1; i<=n; i++){
rt[i] = dgb_SEG::modify(rt[0], 1, n, i, 1);
}
for(int i=1; i<=q; i++){
cin >> opt[i];
if(opt[i] == 'S'){
a[i] = read(), b[i] = read();
rt[a[i]] = rt[b[i]] = dgb_SEG::merge(rt[a[i]], rt[b[i]], 1, n);
} else if(opt[i] == 'Q'){
a[i] = read(), b[i] = read();
ans[i] = dgb_SEG::singleQuery(rt[a[i]], 1, n, b[i]);
} else {
a[i] = read();
}
}
dgb_SEG::clear();
for(int i=1; i<=n; i++) {
rt[i] = ++dgb_SEG::tp;
}
for(int i=q; i>=1; i--){
if(opt[i] == 'S'){
rt[a[i]] = dgb_SEG::modify(rt[a[i]], 1, q, i, 1);
rt[a[i]] = rt[b[i]] = dgb_SEG::merge(rt[a[i]], rt[b[i]], 1, q);
}
}
// for(int i=1; i<=q; i++){
// printf("%lld\n", dgb_SEG::multiQuery(rt[i], 1, q, 1, q)+1);
// }
for(int i=1; i<=q; i++){
// printf("%d: ", i);
if(opt[i] == 'Q'){
printf(ans[i] ? "yes\n" : "no\n");
} else if(opt[i] == 'C'){
printf("%lld\n", dgb_SEG::multiQuery(rt[a[i]], 1, q, 1, i)+1);
}
}
}