Team Extra Contest 2022-10-21补题

D. 38 parrots

线段树

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define rep(a, b, c) for(int (a)=(b);(a)<=(c);(a)++)
#define per(a, b, c) for(int (a)=(b);(a)>=(c);(a)--)
#define mset(var, val) memset(var,val,sizeof(var))
#define ll long long
#define fi first
#define se second
#define no "N"
#define yes "Y"
#define pb push_back
#define endl "\n"
#define pii pair<int,int>
#define pll pair<ll,ll>

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1.0);

vector<ll>v(N,0);
int n;

struct Node{
    int l,r,v;
}tr[N<<2];
void build(int u,int l,int r){
    tr[u]={l,r,1};
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void push_up(int u){tr[u].v=__gcd(tr[u<<1].v,tr[u<<1|1].v);}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].v;
    int mid=(tr[u].l+tr[u].r)>>1,v=0;
    if(l<=mid)v=query(u<<1,l,r);
    if(r>mid)v=__gcd(v,query(u<<1|1,l,r));
    return v;
}
void modify(int u,int x,int v){
    if(tr[u].l==x&&tr[u].r==x)tr[u].v=v;
    else{
        int mid=(tr[u].l+tr[u].r)>>1;
        if(x<=mid)modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        push_up(u);
    }
}

bool find(int x,int l,int r){
    for(int i=l;i<r;i++){
        if(v[i]==x) return true;
    }
    return false;
}

void solve() {
    int x,l=1,r=1;
    char c;
    cin>>n;
    build(1,1,n);
    rep(i,1,n){
        cin>>c;
        if(c=='+'){
            cin>>x;
            v[r]=x;
            modify(1,r,x);
            r++;
        }else if(c=='?'){
            ll fd= query(1,l,max(l,r-1));
            if(find(fd,l,r)){
                cout<<yes<<fd<<endl;
            }else{
                cout<<no<<endl;
            }
        }else{
            l++;
        }
    }
}

int main() {
    IOS;
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}