01字典树 HDU4825
题意：给定长度为n的数组a，做m次询问，每次给定一个正整数x，询问数组a中与x做异或运算值最大的数。
（ps，这模板可扩展性挺强的）
#include <bits/stdc++.h>
using namespace std;
//#define int long long 抄袭不好
const int N = 5e5 + 5;
int nxt[N*30][2], cnt;
int val[N];
int a[N];
void init()
{
nxt[0][0]=0;
nxt[0][1]=0;
cnt=1;
}
void add(int n)
{
int p=0;
for (int i=20;i>=0;--i)
{
int bit=(n>>i)&1;
if(!nxt[p][bit])
{
nxt[cnt][0]=nxt[cnt][1] = 0;
nxt[p][bit]=cnt++;
}
p = nxt[p][bit];
}
val[p] = n;
}
int q_max(int x)
{
int p=0;
for(int i=20;i>=0;i--)
{
int bit=((x>>i)&1);
if(nxt[p][bit^1])
{
p=nxt[p][bit^1];
}
else
{
p=nxt[p][bit];
}
}
return val[p];
}
int main()
{
int t;
for(cin>>t;t;t--)
{
init();
int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++)
{
cin>>a[i];
add(a[i]);
}
int m;
cin>>m;
for(int i=1;i<=m;i++)
{
int temp;
cin>>temp;
cout<<q_max(temp)<<endl;
}
}
return 0;
}
D2. 388535 (Hard Version)
难度2300
数据结构+思维
题意：给定l,r两个数值和一个长度为r-l+1的数组a，要求选择定一个值x，让a整个数组都异或x之后得到的新的数组a，a成为包含[l,r]区间所有元素的一个排列。
思路：
0，ok，题目保证这样的x必然存在也就是说a数组中不可能含有两个相同的值（我觉得a数组还应该是一段连续的区间值，不过这不重要）
1 既然a中元素无重复，显然对于x异或之后也不重复
2 利用01字典树来枚举x，令x异或整个数组之后最大值为r最小值为l就可以了。
然后交上去发现TLE
3.考虑优化，异或满足交换律性质，所以对于x有a[i] ^ x=l，那么就是a[i] ^ l=x，所以x可以由a[i]^ l推出由原本的 2 17*logn优化为n * logn，发现在可接受范围内。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int nxt[N*30][2], cnt;
int val[N];
int a[N];
void init()
{
nxt[0][0]=0;
nxt[0][1]=0;
cnt=1;
}
void add(int n)
{
int p=0;
for (int i=20;i>=0;--i)
{
int bit=(n>>i)&1;
if(!nxt[p][bit])
{
nxt[cnt][0]=nxt[cnt][1] = 0;
nxt[p][bit]=cnt++;
}
p = nxt[p][bit];
}
val[p] = n;
}
int q_max(int x)
{
int p=0;
for(int i=20;i>=0;i--)
{
int bit=((x>>i)&1);
if(nxt[p][bit^1])
{
p=nxt[p][bit^1];
}
else
{
p=nxt[p][bit];
}
}
return val[p]^x;
}
int q_min(int x)
{
int p=0;
for(int i=20;i>=0;i--)
{
int bit=((x>>i)&1);
if(nxt[p][bit])
{
p=nxt[p][bit];
}
else
{
p=nxt[p][bit^1];
}
}
return val[p]^x;
}
int main()
{
int t;
for(cin>>t;t;t--)
{
init();
int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++)
{
cin>>a[i];
add(a[i]);
}
for(int i=l;i<=r;i++)
{
int x=a[i]^l;
if(q_max(x)==r&&q_min(x)==l)
{
cout<<x<<endl;
break;
}
}
}
return 0;
}
C - Cut 'em all!
难度 1600
题意：给定一棵以1节点为根的树，问最多砍掉几条边能让断开后的所有部分的节点数为偶数
思路：
1.总节点数为奇数无答案输出-1
2.假设节点数量为2的子树是整颗数中不能再细分的最小节点数量为偶数的子树，那么我们砍掉这课“最小子树”其实对其他的节点能产生的答案并不会有影响。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
struct node
{
int nex,to;
};
node edge[N<<1];
int head[N],tot;
int fa[N];
int siz[N];
int ans;
void add(int from,int to)
{
edge[++tot].to=to;
edge[tot].nex=head[from];
head[from]=tot;
}
void DFS(int now,int fath)
{
siz[now]=1;
for(int i=head[now];i;i=edge[i].nex)
{
if(edge[i].to==fath)
continue;
DFS(edge[i].to,now);
if(siz[edge[i].to]%2)
siz[now]+=siz[edge[i].to];
}
if(siz[now]%2==0)
ans++;
}
signed main()
{
int n;
cin>>n;
if(n%2)
{
cout<<"-1"<<endl;
return 0;
}
for(int i=1,l,r;i<=n-1;i++)
{
cin>>l>>r;
add(l,r);
add(r,l);
}
DFS(1,0);
cout<<ans-1<<endl;
return 0;
}
双tag线段树
考虑每个tag之间的影响关系，高优先的tag会影响低优先的tag所以在低优先tag的修改过程中也要先一步考虑高优先tag的操作。
P1253
#include <bits/stdc++.h>
using namespace std;
#define maxn 1100000
#define ls p<<1
#define rs p<<1|1
#define ll long long
ll ans[maxn<<2],tag[maxn<<2],a[maxn],tag2[maxn<<2];
ll nl,nr,k;
void up(int p)
{
ans[p]=max(ans[ls],ans[rs]);
}
void bulid(int l,int r,int p)
{
if(l==r)
{
tag2[p]=-1145141919810;
tag[p]=0;
ans[p]=a[l];
return ;
}
int mid=(l+r)>>1;
bulid(l,mid,ls);
bulid(mid+1,r,rs);
up(p);
}
void down2(int p)
{
if(tag2[p]!=-1145141919810)
{
tag[rs]=tag[ls]=0;
ans[ls]=tag2[p];ans[rs]=tag2[p];
tag2[ls]=tag2[p];tag2[rs]=tag2[p];
tag2[p]=-1145141919810;
}
}
void down1(int p)
{
down2(p);
ans[ls]+=tag[p];ans[rs]+=tag[p];
tag[ls]+=tag[p];tag[rs]+=tag[p];
tag[p]=0;
}
void down(int p)
{
down2(p);
down1(p);
}
void fix1(int l,int r,int p)
{
if(nl<=l&&r<=nr)
{
down2(p);
ans[p]+=k;
tag[p]+=k;
return ;
}
down(p);
int mid=(l+r)>>1;
if(nl<=mid)
fix1(l,mid,ls);
if(nr>mid)
fix1(mid+1,r,rs);
up(p);
}
void fix2(int l,int r,int p)
{
if(nl<=l&&r<=nr)
{
tag[p]=0;
ans[p]=k;
tag2[p]=k;
return ;
}
down(p);
int mid=(l+r)>>1;
if(nl<=mid)
fix2(l,mid,ls);
if(mid<nr)
fix2(mid+1,r,rs);
up(p);
}
ll query(int l,int r,int p)
{
ll res=-1000000000000000000;
if(nl<=l&&nr>=r)
{
return ans[p];
}
down(p);
int mid=(l+r)>>1;
if(nl<=mid)
res=max(res,query(l,mid,ls));
if(nr>mid)
res=max(res,query(mid+1,r,rs));
return res;
}
int main()
{
int n,m,c;
//freopen("in.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
bulid(1,n,1);
for(int i=1;i<=n*4;i++)
tag2[i]=-1145141919810;
for(int i=1;i<=m;i++)
{
scanf("%d",&c);
if(c==1)
{
scanf("%lld%lld%lld",&nl,&nr,&k);
fix2(1,n,1);
}
if(c==2)
{
scanf("%lld%lld%lld",&nl,&nr,&k);
fix1(1,n,1);
}
if(c==3)
{
scanf("%lld%lld",&nl,&nr);
printf("%lld\n",query(1,n,1));
}
}
return 0;
}
