---恢复内容开始---
HAOI 2019 DAY1 T1 我爆零了。
爆零的感觉很难受 原因竟然是我从没犯过的错误 审题不清。情绪低迷。
也许 也许 也许就是想让我知道我有多菜吧。
求前k大的区间异或值 。我硬生生读错题目 想着将区间分成k段 求划分整个区间的最大值。
我还写了一个n^3的dp 觉得只能过60 然后搞了一棵trie树 觉得能过80 然后 发现GG了
这个读错题的我就非常的毒瘤了。 我的RP可能是谷底了吧。
这个范围 60分随便写啊 n^2暴力 然后 放堆里出来k个即可。
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
char buf[<<],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;
}
inline ll read()
{
ll x=,f=;char ch=getc();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}
return x*f;
}
inline void put(ll x)
{
x<?putchar('-'),x=-x:;
ll num=;char ch[];
while(x)ch[++num]=x%+'',x/=;
num==?putchar(''):;
while(num)putchar(ch[num--]);
putchar('\n');return;
}
const ll MAXN=;
ll n,k,ans;
ll a[MAXN],w[MAXN];
priority_queue<ll> q;
int main()
{
//freopen("1.in","r",stdin);
n=read();k=read();
for(ll i=;i<=n;++i)
{
a[i]=read();
w[i]=(a[i]^w[i-]);
q.push(w[i]);
}
for(ll i=;i<=n;++i)
for(ll j=i+;j<=n;++j)
{
ll x=(w[i]^w[j]);
q.push(x);
}
for(ll i=;i<=k;++i)
{
ans+=q.top();
q.pop();
}
put(ans);
return ;
}
考虑正解 首先构建01trie 自然 考虑如何求出第k大 好像不太好求 因为我好像没办法标记 或者说标记某个东西用过了的话会很困难的。
所以这时 可持久化trie 就出来了 也很自然吧 像主席树一般。
求第k大这不秒了么，主席树就是来求第k大的 然后 每次根据某个右端点求出左端点即可。
很简单的题目我却因为 种种非常蠢的原因爆零 甚至连 60都搞不到真是服气我自己 机会不多，自己不珍惜那么 将会永远后悔。
值得一提的是 这道题在loj上我自己写的大常数代码秒过但是洛谷上就 一直T
各种优化常数 这里我总结一下T一个点或几个点的优化方法：
1 不要将所有的 int 都换成long long 这样会很慢的。
2 加上inline Register
3 空间开的不要过大
4 一些不需要的代码可以优化的要进行优化。
// luogu-judger-enable-o2
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#include<cmath>
#define ll long long
#define R register
using namespace std;
char buf[<<],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;
}
inline ll read()
{
ll x=,f=;char ch=getc();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}
return x*f;
}
inline void put(ll x)
{
x<?putchar('-'),x=-x:;
ll num=;char ch[];
while(x)ch[++num]=x%+'',x/=;
num==?putchar(''):;
while(num)putchar(ch[num--]);
putchar('\n');return;
}
const ll MAXN=,maxn=;
ll n,k,ans,cnt,sum;
ll w[MAXN];
int root[MAXN],rank[MAXN];
int trie[MAXN*maxn][],sz[MAXN*maxn];
priority_queue<pair<ll,int> > b;
inline void insert(int &now,int last,int depth,ll x)
{
if(!now)now=++cnt;
if(depth==)
{
sz[now]++;
sz[now]+=sz[last];
return;
}
int tn=(x>>(depth-))&;
trie[now][tn^]=trie[last][tn^];
insert(trie[now][tn],trie[last][tn],depth-,x);
sz[now]=sz[trie[now][tn]]+sz[trie[now][tn^]];
return;
}
inline void find(int now,int k,int depth,ll x)
{
//if((!trie[now][0])&&(!trie[now][1]))return;
if(depth==)return;
ll tn=(x>>(depth-))&;
if(sz[trie[now][tn^]]>=k)
{
ans=(ans<<)|;
find(trie[now][tn^],k,depth-,x);
}
else
{
ans=ans<<;
find(trie[now][tn],k-sz[trie[now][tn^]],depth-,x);
}
return;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();k=read();
for(R int i=;i<=n;++i)
{
ll x=read();
rank[i]=;
w[i]=(x^w[i-]);
}
insert(root[],root[],,);
for(R int i=;i<=n;++i)insert(root[i],root[i-],,w[i]);
for(R int i=;i<=n;++i)
{
ans=;
find(root[i],rank[i],,w[i]);
++rank[i];
b.push(make_pair(ans,i));
//put(ans);
}
for(R int i=;i<=k;++i)
{
int l=b.top().second;
ll z=b.top().first;
b.pop();sum+=z;//put(z);
ans=;
find(root[l],rank[l],,w[l]);
++rank[l];
b.push(make_pair(ans,l));
}
put(sum);
return ;
}
要是我能刷到这道题 也不至于会爆零了吧 我会证明我有坚强的毅力刷这个题库的。
再次看错了题目 两个数之间的异或最大值并非一段区间的最大值。
这样的话就会比上面的题目就比较简单了。
/**************************************************************
Problem: 3689
User: chdy
Language: C++
Result: Accepted
Time:5056 ms
Memory:43884 kb
****************************************************************/ //#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#include<cmath>
#define ll long long
#define INF -1
using namespace std;
char buf[<<],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;
}
inline int read()
{
int x=,f=;char ch=getc();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}
return x*f;
}
inline void put(int x)
{
x<?putchar('-'),x=-x:;
int num=;char ch[];
while(x)ch[++num]=x%+'',x/=;
num==?putchar(''):;
while(num)putchar(ch[num--]);
putchar(' ');return;
}
const int MAXN=,maxn=;
int n,k,cnt,ans;
int sz[MAXN*maxn],root[MAXN],rank[MAXN];
int a[MAXN],trie[MAXN*maxn][];
struct wy
{
int x,z;
friend int operator <(wy a,wy b){return a.z>b.z;}
};
priority_queue<wy>q;
inline void insert(int &now,int last,int depth,int x)
{
if(!now)now=++cnt;
if(depth==)
{
sz[now]++;
sz[now]+=sz[last];
return;
}
int tn=(x>>(depth-))&;
trie[now][tn^]=trie[last][tn^];
insert(trie[now][tn],trie[last][tn],depth-,x);
sz[now]=sz[trie[now][tn]]+sz[trie[now][tn^]];
return;
}
inline void find(int now,int depth,int k,int x)
{
if(depth==)return;
if(sz[trie[now][]]+sz[trie[now][]]<k){ans=INF;return;}
int tn=(x>>(depth-))&;
if(sz[trie[now][tn]]>=k)
{
ans=ans<<;
find(trie[now][tn],depth-,k,x);
}
else
{
ans=ans<<|;
find(trie[now][tn^],depth-,k-sz[trie[now][tn]],x);
}
return;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();k=read();
for(int i=;i<=n;++i)a[i]=read(),rank[i]=;
for(int i=;i<=n;++i)insert(root[i],root[i-],,a[i-]);
for(int i=;i<=n;++i)
{
ans=;
find(root[i],,rank[i],a[i]);
++rank[i];
q.push((wy){i,ans});
}
for(int i=;i<=k;++i)
{
int l=q.top().x;
int xx=q.top().z;
q.pop();ans=;
if(i!=k)put(xx);
else printf("%d\n",xx);
find(root[l],,rank[l],a[l]);
++rank[l];
if(ans!=-)q.push((wy){l,ans});
}
return ;
}
这道题就是典型的 可持久化trie 树的应用了 当然 比较基础。
因为这些都不带修改 带修改的trie树 可能 就可以树套树了 像带修改的主席树一般。
针对这道题 求 A[p]~A[N]^x之间的最大异或和 考虑 取前缀和那么问题转换成了 w[N]^x^w[p-1];
至于 p的范围 l~r之间 所以p-1 就是l-1~r-1之间了 取决策时 只需在r-1这个trie树上取。
至于l-1 让r-1 - l-2的值 然后判断是否可走即可。
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#include<cmath>
#define ll long long
#define R register
using namespace std;
char buf[<<],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;
}
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void put(int x)
{
x<?putchar('-'),x=-x:;
int num=;char ch[];
while(x)ch[++num]=x%+'',x/=;
num==?putchar(''):;
while(num)putchar(ch[num--]);
putchar('\n');return;
}
const int MAXN=,maxn=;
int n,m,cnt,ans;
int trie[MAXN*maxn][],sz[MAXN*maxn];
int w[MAXN],root[MAXN];
char ch[];
inline void insert(int &now,R int last,R int depth,R int x)
{
if(!now)now=++cnt;
if(!depth)
{
++sz[now];
sz[now]+=sz[last];
return;
}
R int tn=x>>(depth-)&;
trie[now][tn^]=trie[last][tn^];
insert(trie[now][tn],trie[last][tn],depth-,x);
sz[now]=sz[trie[now][tn]]+sz[trie[now][tn^]];
}
inline void find(R int now,R int last,R int depth,R int x)
{
if(!depth)return;
R int tn=x>>(depth-)&;
if(last==-)
{
if(sz[trie[now][tn^]]>)
{
ans=ans<<|;
find(trie[now][tn^],last,depth-,x);
}
else
{
ans=ans<<;
find(trie[now][tn],last,depth-,x);
}
return;
}
if(sz[trie[now][tn^]]-sz[trie[last][tn^]]>)
{
ans=ans<<|;
find(trie[now][tn^],trie[last][tn^],depth-,x);
}
else
{
ans=ans<<;
find(trie[now][tn],trie[last][tn],depth-,x);
}
return;
}
int main()
{
//freopen("1.in","r",stdin);
n=read();m=read();
for(R int i=;i<=n;++i)w[i]=read()^w[i-];
insert(root[],root[],,);
for(R int i=;i<=n;++i)insert(root[i],root[i-],,w[i]);
for(R int i=;i<=m;++i)
{
R int x,l,r;
scanf("%s",ch+);
if(ch[]=='A')
{
x=read();++n;
w[n]=x^w[n-];
insert(root[n],root[n-],,w[n]);
}
else
{
l=read();r=read();x=read();
ans=;
find(root[r-],(l->=)?root[l-]:-,,x^w[n]);
put(ans);
}
}
return ;
}
注意边界 减到-1的处理。。。
当然 书上还有较为简洁的代码，但是我自认为自己代码的常数小所以就不抄书上的代码了。
还是自己写的好！（其实大致思路都是一样的）
可持久化trie 就到这里了 其实真的跟主席树差不多。