题目

题目描述

某神犇正在打splay.one，打出了$0-233$的超鬼战绩，并为之愤怒
神犇怎么可能超鬼呢？
神犇立马黑进了服务器，把if(x≤0) 死亡;（x为生命值）这句话删掉了
神犇觉得不太好，就改成了if(x==0) 死亡；
众所周知神犇沉迷写题不会打游戏，只要$x$有可能为$0$，神犇依然会超鬼
现在神犇正处于混战当中，有$n$个塔，分别为炮塔和治疗塔，每秒只会有一个炮塔对神犇造成伤害或者一个治疗塔给神犇加奶
神犇只会屠题，所以打游戏时便会眼花缭乱，看不清哪个是炮塔哪个是治疗塔
不过因为神犇黑进了服务器，所以他获得了所有塔的伤害量或者奶量
神犇想知道他会不会超鬼

输入格式

两个正整数$n,q$
接下来$n$个整数$A_i$，表示塔的奶量或伤害；
接下来$q$个询问，每次格式如下：
insert x表示加入一个塔，塔的伤害量或奶量；
delete x表示删除一个塔，塔的伤害量或奶量（保证能删）；
ask x表示若神犇的初始生命值为$x$，询问神犇会不会超鬼

输出格式

对于每个询问，如果会输出WTF，否则输出Nice

样例

样例输入

4 6
6 4 2 18
ask 3
insert 9
delete 4
ask 8
delete 2
ask 6

样例输出

1
2
3

Nice 
WTF
WTF

数据范围与提示

$n,q\leqslant 200000$
$a_i \leqslant 10^9$
输入保证任何时候至少有一个塔

题解

~~话说这题和Splay有啥关系呢~~
在不考虑加减炮塔的情况下，这道题就相当于在问你：给你$n+1$个正整数$a_1,a_2,\cdots\cdots a_n$和$b$，是否存在$n$个整数（因为有不同的两种塔，所以不需要一定为正整数）$x_1,x_2,\cdots\cdots x_n$，使得$\sum\limits_{i=1}^na_ix_i=b$
那么，我们由裴蜀定理可以知道：只要$gcd(a_1,a_2,\cdots \cdots,a_n)|b$就有解
所以我们就可以直接用线段树维护gcd就可以了
记得动态开点！
附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
struct ppap
{
    int ls,rs,x,s;
}t[12000000];
int n,q,cnt,root,a[200010];
char op[10];
void change(int &p,int l,int r,int X,int f)
{
    if(!p) p=++cnt;
    if(l==r){	
        t[p].s+=f;
        if(t[p].s) t[p].x=X;
        else t[p].x=0;
        return;
    }
    int mid=(l+r)>>1;
    if(X<=mid) change(t[p].ls,l,mid,X,f);
    else change(t[p].rs,mid+1,r,X,f);
    t[p].x=__gcd(t[t[p].ls].x,t[t[p].rs].x);
    t[p].s=t[t[p].ls].s+t[t[p].rs].s;
} 
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),change(root,1,1e9,a[i],1);
    for(int i=1,x;i<=q;i++){
        scanf(" %s %d",op,&x);
        if(op[0]=='a'){
            if(x%t[root].x==0) printf("WTF\n");
            else printf("Nice\n");
        } 
        else if(op[0]=='i') change(root,1,1e9,x,1);
        else change(root,1,1e9,x,-1);
    }
}