Codeforces Round #532(Div.2) - F. Ivan and Burgers - 선형 베이스
34683 단어 수학.
【Description】
Ivan loves burgers and spending money. There are burger joints on the street where Ivan
lives. Ivan has friends, and the -th friend suggested to meet at the joint li and walk
to the joint ri(li<ri). While strolling with the i-th friend Ivan can visit all joints
which satisfy li<xi<ri.
For each joint Ivan knows the cost of the most expensive burger in it, it costs
burles. Ivan wants to visit some subset of joints on his way, in each of them he will buy
the most expensive burger and spend the most money. But there is a small issue: his card
broke and instead of charging him for purchases, the amount of money on it changes as
follows.
If Ivan had burles before the purchase and he spent burles at the joint, then after
the purchase he would have burles, where denotes the bitwise XOR operation.
Currently Ivan has burles and he wants to go out for a walk. Help him to determine
the maximal amount of burles he can spend if he goes for a walk with the friend . The
amount of burles he spends is defined as the difference between the initial amount on his
account and the final account.
【Input】
The first line contains one integer n (1<=n<=500000) — the number of burger shops.
The next line contains n integers c1,c2,……,cn(0<=ci<=1e6), where ci — the cost of the
most expensive burger in the burger joint .
The third line contains one integer q (1<=q<=500000) — the number of Ivan's friends.
Each of the next lines contain two integers li and ri (1<=li<=ri<=n) — pairs of numbers
of burger shops between which Ivan will walk.
【Output】
Output q lines,i-th of which containing the maximum amount of money Ivan can spend with
the friend i .
【Examples】
Sample Input
4
7 2 3 4
3
1 4
2 3
1 3
Sample Output
7
3
7
Sample Input
5
12 14 23 13 7
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
Sample Output
12
14
27
27
31
14
25
26
30
23
26
29
13
13
7
【Problem Description】
n a1,a2,……,an, q , [l,r], ,
。
【Solution】
, , , a[i] ,i , ,
。 i 。
, i l。
【Code】
/*
* @Author: Simon
* @Date: 2019-03-06 20:00:45
* @Last Modified by: Simon
* @Last Modified time: 2019-03-06 20:26:44
*/
#include
using namespace std;
typedef int Int;
#define int long long
#define INF 0x3f3f3f3f
#define maxn 500005
int a[25],v[maxn],pos[25];
struct node{
int u,v,ord;
bool operator <(const node a)const {
if(v==a.v) return u<a.u;
return v<a.v;
}
}c[maxn];
void insert(int val,int p){//
for(int i=20;~i;i--){
if(val>>i&1LL){
if(!a[i]){
a[i]=val;pos[i]=p;break;//
}
if(p>pos[i]) swap(pos[i],p),swap(a[i],val); //p ,
val^=a[i];
}
}
}
int query(int l){ //
int ans=0;
for(int i=20;~i;i--){
if(pos[i]>=l&&(ans^a[i])>ans) ans^=a[i]; // [l,r]
}
return ans;
}
int ans[maxn];
Int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",v+i);
}
int q;scanf("%lld",&q);
for(int i=1;i<=q;i++) scanf("%lld%lld",&c[i].u,&c[i].v),c[i].ord=i;
sort(c+1,c+q+1);int r=1;
for(int i=1;i<=q;i++){
while(r<=c[i].v){
insert(v[r],r);r++;
}
ans[c[i].ord]=query(c[i].u);
}
for(int i=1;i<=q;i++) printf("%lld
",ans[i]);
cin.get(),cin.get();
return 0;
}
/*
* @Author: Simon
* @Date: 2019-07-23 12:15:12
* @Last Modified by: Simon
* @Last Modified time: 2019-07-23 13:39:15
*/
#include
using namespace std;
typedef int Int;
#define int long long
#define INF 0x3f3f3f3f
#define maxn 500005
int a[maxn],base[maxn][25]/* i */,pos[maxn][25];
void insert(int val,int p){
int k=p;
for(int i=0;i<=20;i++) base[p][i]=base[p-1][i],pos[p][i]=pos[p-1][i]; // p-1 ,
for(int i=20;i>=0;i--) if(val>>i&1){
if(!base[p][i]){
base[p][i]=val;
pos[p][i]=k;
break;
}
if (k > pos[p][i]) {
swap(pos[p][i], k); // , k, p
swap(base[p][i], val);
}
val ^= base[p][i];
}
}
Int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],insert(a[i],i);
int q;cin>>q;
while(q--){
int l,r;cin>>l>>r;
int ans=0;
for(int i=20;i>=0;i--){
if((ans^base[r][i])>ans&&pos[r][i]>=l) ans^=base[r][i];
}
cout<<ans<<endl;
}
cin.get(),cin.get();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Coq에서 증명된 이중 부정 주위의 증명이중 부정 가져오기 이중 부정 해소를 증명할 수 없지만 삼중 부정 해소를 증명할 수 있다 이중 부정 해소의 이중 부정 이중 부정 해소와 배중률 동치 고전 이론을 얻으려면 직관주의 이론에 어느 것을 넣어도 된다는 것이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.