首页 > 代码库 > qwb VS 去污棒

qwb VS 去污棒

2024-09-29 17:47:39   217人阅读

qwb VS 去污棒

Time Limit: 2 Sec  Memory Limit: 256 MB

Description

qwb表白学姐失败后，郁郁寡欢，整天坐在太阳底下赏月。在外人看来，他每天自言自语，其实他在和自己的影子“去污棒”聊天。
去污棒和qwb互相出题考验对方，去污棒问了qwb这样一个问题：
现已知一个有n个正整数的序列a[1],a[2]...a[n],接下来有m个操作

操作一共有两种：

1.在序列末尾添加一个数x。

2.查询suf[p] xor x的最大值，其中xor是异或 ,l<=p<=r，
suf[t]表示从t开始的后缀的异或和，即suf[t]=a[t] xor a[t+1] xor ...xor a[len]，len为序列长度。

Input

第一行一个整数T(<=5)，表示一共有T组数据。

每组数据第一行两个整数n(<=200000),m(<=200000)，意义如上所述。

随后一行有n个数，表示初始序列。
随后m行，每行表示一个操作。
操作有两种，1： x 表示在末尾添加一个x，2： l r x表示查询suf[p] xor x的最大值，其中l<= p <= r，
所有数及x不超过224 且保证所有操作合法。

Output

每组测试数据的第一行输出"Case x:"，x为数据组数的标号，从1开始。

接下来，对每个操作2输出一行答案。

Sample Input

15 51 2 3 4 52 1 3 41 101 72 4 4 52 1 5 19

Sample Output

Case 1:6931
分析：考虑怎样得到后缀，因为后缀会改变，不好修改，而前缀不会改变；
　　　所以维护当前所有数异或sum以及每个前缀异或a[i]，sum^a[i]就得到i+1的后缀了；
　　　区间查询，考虑主席树或莫队，然而莫队复杂度高一点，不能通过这道题；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#include <cassert>#include <ctime>#include<unordered_map>#define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")const int maxn=4e5+10;const int N=5e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,rt[maxn],ls[maxn*20],rs[maxn*20],s[maxn*20],cas,sz;void insert(int x,int &y,int v,int t){    y=++sz;    s[y]=s[x]+1;    if(t==-1)return;    ls[y]=ls[x],rs[y]=rs[x];    int z=(v>>t&1);    if(z==0)insert(ls[x],ls[y],v,t-1);    else insert(rs[x],rs[y],v,t-1);}int gao(int l,int r,int x,int t){    if(t==-1)return 0;    int y=(x>>t&1);    if(y==0)    {        if(s[rs[r]]-s[rs[l]])return (1<<t)+gao(rs[l],rs[r],x,t-1);        else return gao(ls[l],ls[r],x,t-1);    }    else    {        if(s[ls[r]]-s[ls[l]])return (1<<t)+gao(ls[l],ls[r],x,t-1);        else return gao(rs[l],rs[r],x,t-1);    }}int main(){    int i,j;    insert(rt[0],rt[0],0,24);    scanf("%d",&t);    while(t--)    {        sz=0;        scanf("%d%d",&n,&m);        int sum=0;        rep(i,1,n)scanf("%d",&j),sum^=j,insert(rt[i-1],rt[i],sum,24);        printf("Case %d:\n",++cas);        rep(i,1,m)        {            int x,y,z,w;            scanf("%d%d",&x,&y);            if(x==1)sum^=y,++n,insert(rt[n-1],rt[n],sum,24);            else scanf("%d%d",&z,&w),printf("%d\n",gao(rt[y-2],rt[z-1],w^sum,24));        }    }    return 0;}

qwb VS 去污棒


联系
我们