BZOJ 2589 Spoj 10707 Count on a tree II 强制在线莫队算法(TLE)
浏览数：23 /
时间：2015年06月08日
题目大意：给定一棵树，每个节点有一个颜色，多次询问某条路径上颜色数量，强制在线
正解是块状数组，强制在线莫队会TLE到死，想AC这道题的不用看了
如果朴素的跑树上莫队其实并不难- - 但是强制在线
因此我们可以考虑强制在线莫队算法
将树分成O(n^1/3)块，每块大小O(n^2/3)
记录每两块之间的答案、每种颜色的出现次数和哪些点被记录到了答案中
每次查询先找到两端点所在块的端点的答案，然后暴力用莫队转移即可
空间复杂度O(n^1/3)*O(n^1/3)*O(n)=O(n^5/3)
预处理时间复杂度O(n^1/3)*O(n^1/3)*O(n)=O(n^5/3)
单次询问时间复杂度O(n^2/3)
然后。。。被卡常数。。。明明本机只要不到11秒就能全部出解。。。BZ渣评测机怎么这么慢。。。
读入优化。。。寻址优化。。。short压内存。。。内嵌汇编强制inline。。。函数改成宏。。。倍增LCA改成RMQLCA。。。三分法修改块的大小。。。还有啥。。。bool改成bitset。。。随机数选根防卡。。。还特意去切了王室联邦练习树分块。。。最后还在结尾附加一段注释增强一下信仰。。。
从早上卡到现在。。。 加上昨天写的版本一共挂了七篇。。。整整七篇。。。。。。。。。。。。。。。。。。。。。
发个本地评测的图吧。。。 此题精神AC了。。。
我が生涯に、一片の悔いなし。。。。。
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 40002
#define B 95
#define Change(x,f,v,ans) { if(v[x]) { if(!--f[a[x]]) --ans; v[x]=0; } else { if(!f[a[x]]++) ++ans; v[x]=1; } }
#define swap(x,y) {int t=x;x=y;y=t;}
using namespace std;
struct abcd{
int to,next;
}table[M<<1];
int head[M],tot;
int n,m,b,cnt,last_ans;
int a[M],fa[M],dpt[M],log2[M<<1],min_dpt[M<<1][20],into[M];
int belong[M],root[M],stack[M],top;
unsigned short f[B*(B-1)/2*M+M];
bitset<M> v[B][B];
int ans[B][B],pos[B][B];
__inline__ __attribute__((always_inline)) void Add(int x,int y)
{
table[++tot].to=y;
table[tot].next=head[x];
head[x]=tot;
}
void DFS(int x)
{
static int T;
int i,bottom=top;
dpt[x]=dpt[fa[x]]+1;
min_dpt[into[x]=++T][0]=x;
for(i=head[x];i;i=table[i].next)
if(table[i].to!=fa[x])
{
fa[table[i].to]=x;
DFS(table[i].to);
if(top-bottom>=b)
{
while(top!=bottom)
belong[stack[top--]]=cnt;
root[cnt++]=x;
}
min_dpt[++T][0]=x;
}
stack[++top]=x;
}
/*
__inline__ __attribute__((always_inline)) void Change(int x,unsigned short f[M],bitset<M> &v,int &ans)
{
if(v[x])
{
if(!--f[a[x]])
--ans;
}
else
{
if(!f[a[x]]++)
++ans;
}
v[x]=!v[x];
}
*/
void Pretreatment(int x,int y,unsigned short f[M],bitset<M> &v,int &ans)
{
if(dpt[x]<dpt[y])
swap(x,y);
while(dpt[x]>dpt[y])
{
Change(x,f,v,ans);
x=fa[x];
}
while(x!=y)
{
Change(x,f,v,ans);
Change(y,f,v,ans);
x=fa[x];y=fa[y];
}
}
__inline__ __attribute__((always_inline)) int Min(int x,int y)
{
return dpt[x]<dpt[y]?x:y;
}
__inline__ __attribute__((always_inline)) int LCA(int x,int y)
{
x=into[x];y=into[y];
if(x>y) swap(x,y);
int j=log2[y-x+1];
return Min(min_dpt[x][j],min_dpt[y-(1<<j)+1][j]);
}
int Query(int x,int y)
{
static unsigned short f[M];
static bitset<M> v;
static int tim1[M],tim2[M],T;++T;
if(belong[x]>belong[y])
swap(x,y);
unsigned short *F=::f+pos[belong[x]][belong[y]];
bitset<M> &V=::v[belong[x]][belong[y]];
int ans=::ans[belong[x]][belong[y]];
int l=root[belong[x]],r=root[belong[y]];
unsigned short temp,a_t,lca=LCA(l,x);
for(int temp=x;temp!=lca;temp=fa[temp])
{
a_t=a[temp];
if(tim1[a_t]!=T)
tim1[a_t]=T,f[a_t]=F[a_t];
if(tim2[temp]!=T)
tim2[temp]=T,v[temp]=V[temp];
Change(temp,f,v,ans);
}
for(temp=l;temp!=lca;temp=fa[temp])
{
a_t=a[temp];
if(tim1[a_t]!=T)
tim1[a_t]=T,f[a_t]=F[a_t];
if(tim2[temp]!=T)
tim2[temp]=T,v[temp]=V[temp];
Change(temp,f,v,ans);
}
lca=LCA(r,y);
for(temp=y;temp!=lca;temp=fa[temp])
{
a_t=a[temp];
if(tim1[a_t]!=T)
tim1[a_t]=T,f[a_t]=F[a_t];
if(tim2[temp]!=T)
tim2[temp]=T,v[temp]=V[temp];
Change(temp,f,v,ans);
}
for(temp=r;temp!=lca;temp=fa[temp])
{
a_t=a[temp];
if(tim1[a_t]!=T)
tim1[a_t]=T,f[a_t]=F[a_t];
if(tim2[temp]!=T)
tim2[temp]=T,v[temp]=V[temp];
Change(temp,f,v,ans);
}
temp=LCA(x,y);
a_t=a[temp];
if(tim1[a_t]!=T)
tim1[a_t]=T,f[a_t]=F[a_t];
if(tim2[temp]!=T)
tim2[temp]=T,v[temp]=V[temp];
Change(temp,f,v,ans);
return ans;
}
namespace IStream{
const int L=1<<15;
char buffer[L],*S,*T;
char Get_Char()
{
if(S==T)
{
T=(S=buffer)+fread(buffer,1,L,stdin);
if(S==T) return EOF;
}
return *S++;
}
int Get_Int()
{
char c;
int re=0;
for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
while(c>='0'&&c<='9')
re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
return re;
}
}
class OStream{
private:
static const int L=1<<15;
char stack[20];int top;
char buffer[L],*S;
public:
OStream()
{
S=buffer;
}
void Put_Int(int x,bool flag)
{
if(flag) stack[++top]='\n';
if(!x) stack[++top]='0';
else while(x)
stack[++top]=x%10+'0',x/=10;
while(top)
{
if(S==buffer+L-1)
{
//fwrite(buffer,1,S-buffer,stdout);
printf("%s",buffer);
S=buffer;
}
*S++=stack[top--];
}
}
~OStream()
{
//fwrite(buffer,1,S-buffer,stdout);
*S=0;printf("%s",buffer);
}
}os;
int main()
{
#ifndef ONLINE_JUDGE
freopen("2589.in","r",stdin);
freopen("2589.out","w",stdout);
#endif
static pair<int,int*> b[M];
int i,j,x,y;
cin>>n>>m;
::b=420;
for(i=1;i<=n;i++)
b[i].first=IStream::Get_Int(),b[i].second=&a[i];
sort(b+1,b+n+1);
for(i=1;i<=n;i++)
{
static int tot=0;
if(i==1||b[i].first!=b[i-1].first)
++tot;
*b[i].second=tot;
}
for(i=1;i<n;i++)
{
x=IStream::Get_Int();
y=IStream::Get_Int();
Add(x,y);Add(y,x);
}
int r=6854654%n+1;
DFS(r);
if(!cnt) root[cnt++]=r;
while(top)
belong[stack[top--]]=cnt-1;
log2[0]=-1;
for(i=1;i<=n-1<<1;i++)
log2[i]=log2[i>>1]+1;
for(j=1;j<=log2[n-1<<1];j++)
for(i=1;i+(1<<j)-1<=n-1<<1;i++)
min_dpt[i][j]=Min(min_dpt[i][j-1],min_dpt[i+(1<<j-1)][j-1]);
for(i=0;i<cnt;i++)
for(j=i+1;j<cnt;j++)
{
static int T;
pos[i][j]=(++T)*M;
if(j==i+1)
Pretreatment(root[i],root[j],f+pos[i][j],v[i][j],ans[i][j]);
else
{
memcpy(f+pos[i][j],f+pos[i][j-1],sizeof(unsigned short)*M);
v[i][j]=v[i][j-1];
ans[i][j]=ans[i][j-1];
Pretreatment(root[j],root[j-1],f+pos[i][j],v[i][j],ans[i][j]);
}
}
for(i=1;i<=m;i++)
{
x=IStream::Get_Int()^last_ans;
y=IStream::Get_Int();
os.Put_Int(last_ans=Query(x,y),i<m);
}
/*
os.Put_Int(2147483647,true);
sort(root,root+cnt);
for(i=0;i<cnt;i++)
os.Put_Int(root[i],true);
*/
return 0;
}
/*
アナタガ望ムノナラバ
犬ノヤウニ従顺ニ
纽ニ縄ニ锁ニ
缚ラレテアゲマセウ
*/
卡常数狗我操你妈。
总有一天我会用莫队算法卡过这道题的。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
