2020-08-03
http://icpc.upc.edu.cn/problem.php?cid=1461&pid=2
题目描述¶
校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作： K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同 K=2，读入l,r表示询问l~r之间能见到多少种树 （l,r>0）
输入¶
第一行n,m表示道路总长为n，共有m个操作 接下来m行为m个操作
输出¶
对于每个k=2输出一个答案
样例输入¶
样例输出'¶
提示¶
20%的数据保证，n,m<=100 60%的数据保证，n <=1000,m<=50000 100%的数据保证，n,m<=50000 采用括号序列+树状数组来解决这道题目，种树为一个区间，我们可以在种树的起点标记一个左括号，种树的终点标记一个右括号，统计的时候计算终点前左括号的数目和起点前右括号的数目，两个做差即为答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c1[500500]={0};
ll c2[500500]={0};
ll n,m;
ll lowbit(ll x)
{
return x&(-x);
}
ll update1(ll k,ll x)
{
for(ll i=k;i<=n;i+=lowbit(i))
c1[i]+=x;
}
ll update2(ll k,ll x)
{
for(ll i=k;i<=n;i+=lowbit(i))
c2[i]+=x;
}
ll sum1(ll k)
{
ll ans=0;
for(ll i=k;i>=1;i-=lowbit(i))
ans+=c1[i];
return ans;
}
ll sum2(ll k)
{
ll ans=0;
for(ll i=k;i>=1;i-=lowbit(i))
ans+=c2[i];
return ans;
}
int main()
{
ll a,b,c;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
if(a==1)
{
update1(b,1); /// 左括号
update2(c,1); /// 右括号
}
else
{
printf("%lld\n",sum1(c)-sum2(b-1));
}
}
}
题目描述¶
有一个n个元素的数组，每个元素初始均为0。有m条指令，要么让其中一段连续序列数字反转——0变1，1变0（操作1），要么询问某个元素的值（操作2）。
例如当n=20时，10条指令如下：
输入¶
第一行包含两个整数n,m，表示数组的长度和指令的条数； 以下m行，每行的第一个数t表示操作的种类： 若t=1，则接下来有两个数L,R，表示区间[L,R]的每个数均反转； 若t=2，则接下来只有一个数i，表示询问的下标。
输出¶
每个操作2输出一行（非0即1），表示每次操作2的回答。
样例输入¶
样例输出¶
提示¶
对于50%的数据，1≤n≤103,1≤m≤104； 对于100%的数据，1≤n≤105,1≤m≤5×105，保证L≤R。 与上一道题目同，树状数组统计反转次数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c1[500500]={0};
ll c2[500500]={0};
ll p[500500]={0};
ll n,m;
ll lowbit(ll x)
{
return x&(-x);
}
ll update1(ll k,ll x)
{
for(ll i=k;i<=n;i+=lowbit(i))
c1[i]+=x;
}
ll update2(ll k,ll x)
{
for(ll i=k;i<=n;i+=lowbit(i))
c2[i]+=x;
}
ll sum1(ll k)
{
ll ans=0;
for(ll i=k;i>=1;i-=lowbit(i))
ans+=c1[i];
return ans;
}
ll sum2(ll k)
{
ll ans=0;
for(ll i=k;i>=1;i-=lowbit(i))
ans+=c2[i];
return ans;
}
int main()
{
ll a,b,c;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++)
{
scanf("%lld",&a);
if(a==1)
{
scanf("%lld%lld",&b,&c);
update1(b,1); /// 左括号
update2(c,1); /// 右括号
}
else
{
scanf("%lld",&b);
printf("%lld\n",(sum1(b)-sum2(b-1))%2);
}
}
}
题目描述¶
在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？
输入¶
第一行一个整数N，第二行N个整数A1～AN。
输出¶
一个整数表示答案。
样例输入¶
样例输出¶
提示¶
对于100%的数据: N<=10^5, 0<=Ai<2^31。 用字典树存二进制，找最大的异或值。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1005000]={0};
int tree[5000500][3]={0};
int tot=1;///必须从1开始
int in(int x)
{
int p=1;
for(int i=30;i>=0;i--)
{
int k=x>>i&1;
if(tree[p][k]==0)
tree[p][k]=++tot;
p=tree[p][k];
}
}
int out(int x)
{
int p=1,ans=0;
for(int i=30;i>=0;i--)
{
int k=x>>i&1;
if(tree[p][!k])
{
ans=ans*2+!k;
p=tree[p][!k];
}
else
{
ans=ans*2+k;
p=tree[p][k];
}
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int max1=0;
for(int i=1;i<=n;i++)
{
in(a[i]);
int num=out(a[i]);
max1=max(max1,num^a[i]);
}
cout<<max1<<endl;
return 0;
}