【BZOJ 4103】 4103: [Thu Summer Camp 2015]异或运算 (可持久化Trie)

4103: [Thu Summer Camp 2015]异或运算

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 474  Solved: 258

Description

给定长度为n的数列X={x1,x2,...,xn}和长度为m的数列Y={y1,y2,...,ym},令矩阵A中第i行第j列的值Aij=xi xor  yj,每次询问给定矩形区域i∈[u,d],j∈[l,r],找出第k大的Aij。

Input

第一行包含两个正整数n,m,分别表示两个数列的长度

第二行包含n个非负整数xi
第三行包含m个非负整数yj
第四行包含一个正整数p,表示询问次数
随后p行,每行均包含5个正整数,用来描述一次询问,每行包含五个正整数u,d,l,r,k,含义如题意所述。

Output

共p行,每行包含一个非负整数,表示此次询问的答案。

Sample Input

3 3
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4

Sample Output

6
5
1

HINT

对于100%的数据,0<=Xi,Yj<2^31,

1<=u<=d<=n<=1000,
1<=l<=r<=m<=300000,
1<=k<=(d-u+1)*(r-l+1),
1<=p<=500

Source

【分析】

  要膜一膜Po姐:【BZOJ 4103】 4103: [Thu Summer Camp 2015]异或运算 (可持久化Trie)

  好了,这个是。。。异或运算。每一位的运算都和下一位无关的。

  当n=1,你只要根据m个数建一个可持久化TRIE。然后询问的时候就试着填1看看足不足k什么的。

  跟平时不一样的是,现在你是手上拿着个a1之后询问的,你只要每次看一看a1这一位是什么,然后判断填1还是0,如果a1这一位是1就要0、1互换一下嘛。。

  然后n不等于1,其实也很小,相当于1000个TRIE?当然是不用建1000个TRIE的【你也建不了吧?

  只是你现在手上拿着1000个ai,一起询问什么的。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1010
#define Maxm 300010
#define Maxd 30 int a[Maxn]; int rt[Maxm],tot=;
struct node {int lc,rc,cnt;}tr[Maxm*]; void add(int id,int x)
{
rt[id]=++tot;int y=rt[id-];
int nw=rt[id];
for(int i=Maxd;i>=;i--)
{
int ind=x>>i;x&=(<<i)-;
if(!ind)
{
tr[nw].lc=++tot;
tr[tot].cnt=tr[tr[y].lc].cnt+;
tr[nw].rc=tr[y].rc;
nw=tr[nw].lc;y=tr[y].lc;
}
else
{
tr[nw].rc=++tot;
tr[tot].cnt=tr[tr[y].rc].cnt+;
tr[nw].lc=tr[y].lc;
nw=tr[nw].rc;y=tr[y].rc;
}
}
} int nl[Maxn],nr[Maxn];
int query(int ll,int rr,int l,int r,int k)
{
int ans=;
// l=rt[l-1];r=rt[r];
for(int i=ll;i<=rr;i++) nl[i]=rt[l-],nr[i]=rt[r];
for(int i=Maxd;i>=;i--)
{
int x=;
for(int j=ll;j<=rr;j++)
{
int y=a[j]&(<<i);y>>=i;
if(y==) x+=tr[tr[nr[j]].lc].cnt-tr[tr[nl[j]].lc].cnt;
else x+=tr[tr[nr[j]].rc].cnt-tr[tr[nl[j]].rc].cnt;
}
if(x>=k)
{
l=tr[l].lc;r=tr[r].lc;
for(int j=ll;j<=rr;j++)
{
int y=a[j]&(<<i);y>>=i;
if(y==) nl[j]=tr[nl[j]].lc,nr[j]=tr[nr[j]].lc;
else nl[j]=tr[nl[j]].rc,nr[j]=tr[nr[j]].rc;
}
}
else
{
k-=x;
ans|=<<i;
for(int j=ll;j<=rr;j++)
{
int y=a[j]&(<<i);y>>=i;
if(y==) nl[j]=tr[nl[j]].rc,nr[j]=tr[nr[j]].rc;
else nl[j]=tr[nl[j]].lc,nr[j]=tr[nr[j]].lc;
}
}
}
return ans;
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int j=;j<=m;j++)
{
int b;
scanf("%d",&b);
add(j,b);
}
int q;
scanf("%d",&q);
for(int i=;i<=q;i++)
{
int ll,rr,l,r,k;
scanf("%d%d%d%d%d",&ll,&rr,&l,&r,&k);
k=(rr-ll+)*(r-l+)-k+;
printf("%d\n",query(ll,rr,l,r,k));
}
return ;
}

最近已经RE至死。。。

数组开少了2。。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1010
#define Maxm 300010
#define Maxd 30 int a[Maxn]; int rt[Maxm],tot=;
struct node {int lc,rc,cnt;}tr[Maxm*]; void add(int id,int x)
{
rt[id]=++tot;int y=rt[id-];
int nw=rt[id];
for(int i=Maxd;i>=;i--)
{
int ind=x>>i;x&=(<<i)-;
if(!ind)
{
tr[nw].lc=++tot;
tr[tot].cnt=tr[tr[y].lc].cnt+;
tr[nw].rc=tr[y].rc;
nw=tr[nw].lc;y=tr[y].lc;
}
else
{
tr[nw].rc=++tot;
tr[tot].cnt=tr[tr[y].rc].cnt+;
tr[nw].lc=tr[y].lc;
nw=tr[nw].rc;y=tr[y].rc;
}
}
} int nl[Maxn],nr[Maxn];
int query(int ll,int rr,int l,int r,int k)
{
int ans=;
// l=rt[l-1];r=rt[r];
for(int i=ll;i<=rr;i++) nl[i]=rt[l-],nr[i]=rt[r];
for(int i=Maxd;i>=;i--)
{
int x=;
for(int j=ll;j<=rr;j++)
{
int y=a[j]&(<<i);y>>=i;
if(y==) x+=tr[tr[nr[j]].lc].cnt-tr[tr[nl[j]].lc].cnt;
else x+=tr[tr[nr[j]].rc].cnt-tr[tr[nl[j]].rc].cnt;
}
if(x>=k)
{
l=tr[l].lc;r=tr[r].lc;
for(int j=ll;j<=rr;j++)
{
int y=a[j]&(<<i);y>>=i;
if(y==) nl[j]=tr[nl[j]].lc,nr[j]=tr[nr[j]].lc;
else nl[j]=tr[nl[j]].rc,nr[j]=tr[nr[j]].rc;
}
}
else
{
k-=x;
ans|=<<i;
for(int j=ll;j<=rr;j++)
{
int y=a[j]&(<<i);y>>=i;
if(y==) nl[j]=tr[nl[j]].rc,nr[j]=tr[nr[j]].rc;
else nl[j]=tr[nl[j]].lc,nr[j]=tr[nr[j]].lc;
}
}
}
return ans;
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int j=;j<=m;j++)
{
int b;
scanf("%d",&b);
add(j,b);
}
int q;
scanf("%d",&q);
for(int i=;i<=q;i++)
{
int ll,rr,l,r,k;
scanf("%d%d%d%d%d",&ll,&rr,&l,&r,&k);
k=(rr-ll+)*(r-l+)-k+;
printf("%d\n",query(ll,rr,l,r,k));
}
return ;
}

2017-04-08 14:47:45

上一篇:7.Linux查找目录下的所有文件中是否含有某个字符串


下一篇:Windows Phone 四、控件模版