注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1103][POI2007]大都市meg  

2014-08-31 21:23:03|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1103: [POI2007]大都市meg

水题
但是写了好久好久。。。
各种TLE Orz
LCT版
因为据说时间复杂度相对优而且最近刚写了不少LCT
其实是链剖忘光了
然后无限TLE,似乎是常数问题
呵呵(NMB)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
const int N = 250000+10;
struct Node{
Node();
int d,size,bh;short rflag,sflag;
Node *fa,*ch[2];
short pl(){return this==fa->ch[0]?0:1;}
void push();void count();void set();
}*null,point[N],house[N];int hn=0;
Node *newNode(){
if(hn < N){house[hn]=Node();return &house[hn++];}
return new Node();
}
Node::Node(){fa = ch[0]=ch[1]=null;rflag=sflag =0;d=size=0;}
void Node::set(){size=d=0;sflag=1;}
void Node::push(){
if(this==null)return;
if(rflag){
rflag=0;
swap(ch[0],ch[1]);
ch[0]->rflag^=1;
ch[1]->rflag^=1;
}
if(sflag){
sflag=0;
ch[0]->set();
ch[1]->set();
}
}

int n,m;
void Node::count(){if(this==null)return;size = ch[0]->size+ch[1]->size+d;}
struct LCT{
LCT(){
null = newNode();
null->fa = null->ch[0]=null->ch[1] = null;
}
bool notr(Node *r){return r->fa->ch[0]==r||r->fa->ch[1]==r;}
void rotate(Node *k){
Node *r = k->fa;if(k==null||r==null)return;
r->push();k->push();
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
if(r->fa!=null&&notr(r)) r->fa->ch[r->pl()] = k;
k->fa = r->fa;r->fa = k;
k->ch[x]=r;
r->count();k->count();
}
void splay(Node *r){
for(;notr(r);rotate(r))
if(notr(r->fa))rotate(r->fa->pl()==r->pl()?r->fa:r);
r->push();
}
Node *hello(Node *r){
Node *l = null;
for(;r!=null;l=r,r=r->fa){
splay(r);
(r->ch[1]=l)->fa=r;
r->count();
}return l;
}
Node *root(Node *r){hello(r);splay(r);while(r->ch[0]!=null)r=r->ch[0];return r;}
void changer(Node *r){
hello(r)->rflag^=1;
splay(r);
}
void link(Node *r,Node *l){
changer(r);
r->fa = l;
hello(r);
}
void set(Node *r,Node *l){
changer(r);
hello(l);splay(l);
l->set();
}
int ask(Node *r,Node *l){
changer(r);
hello(l);
splay(l);
return l->size;
}
}lt;
int main(){
int i,j,a,b;
n=scan();
for(i=1;i<=n;i++)point[i]=Node(),point[i].bh=i;
for(i=1;i<n;i++) {
a=scan();b=scan();
Node *r = newNode();
r->d = r->size = 1;r->bh=-i;
lt.link(r,&point[a]);
lt.link(r,&point[b]);
}
m=scan();
for(i=1;i<=m+n-1;i++){
char cc=' ';while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='W'){
a=scan();
printf("%d\n",lt.ask(&point[1],&point[a]));
}else{
a=scan();b=scan();
lt.set(&point[a],&point[b]);
}
}
return 0;
}

树链剖分版
然后无奈只好改链剖QAQ
一开始也各种TLE,结果没想到是因为写挫了- -、
然后读错题以为是区间修改就写了线段树
结果读zky神犇的代码发现实际上的点修改
然后果断改成了树状数组8s->4s

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 250000+100;
const int P = N;
int n,m;
int tree[P],lson[P],rson[P],T;
inline void push(int x,int val){ for(;x<=n;x+=x&-x) tree[x]+=val;}
inline void Build(int l,int r){for(int i=1;i<=n;i++) push(i,1);}
inline int get(int x){ int re=0; for(;x;x-=x&-x) re+=tree[x]; return re;}
inline int ask(int la,int ra){return get(ra)-get(la-1);}
inline void set(int x){push(x,-1);}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
struct Point{
Point(){next=NULL;}
Point *next;int d;
void push(int a){
Point *l = new Point;
l->d = a;l->next=next;
next = l;
}
}point[N];
int que[N],ql,qr,ROOT;
int fa[N],deep[N],size[N];
int ptoi[N],itop[N],top[N],son[N];
//非递归版链剖 -- bfs
void preset(){
ql=1;qr=0;que[++qr] = 1;
deep[1]=1;
while(ql<=qr){
int now = que[ql++];
for(Point *i = point[now].next;i!=NULL;i=i->next)
if(i->d != fa[now]){
fa[i->d] = now;
deep[i->d] = deep[now] +1;
que[++qr] = i->d;
}
}que[0] = qr;
for(int i=que[0];i;i--){
int now = que[i];size[now]=1;
for(Point *l = point[now].next;l!=NULL;l=l->next)
if(l->d!=fa[now]){
size[now]+=size[l->d];
if(size[l->d] > size[son[now]])son[now] = l->d;
}
}
int now = 1;
while(now){
if(!ptoi[now]){
ptoi[now] = ++ptoi[0];
itop[ptoi[0]] = now;
if(now == son[fa[now]])top[now] = top[fa[now]];
else top[now] = now;
if(son[now]) now = son[now];
else now = fa[now];
}else{
Point *&i = point[now].next;
while(i!=NULL&&(i->d==son[now]||i->d==fa[now]))i = i->next;
if(i!=NULL)now = i->d,i=i->next;
else now = fa[now];


}
}
}
int query(int x){
int re=0;
while(top[x]!=1){
re+=ask(ptoi[top[x]],ptoi[x]);
x = fa[top[x]];
//printf("%d\n",x);
}if(x!=1)re+=ask(ptoi[son[1]],ptoi[x]);
return re;
}
void change(int a,int b){
if(deep[b] > deep[a]) a = b;
set(ptoi[a]);
}
int main(){
//freopen("input.txt","r",stdin);
//int start = clock();
int i,j,a,b;
n=scan();
for(i=1;i<n;i++){
a=scan();b=scan();
point[a].push(b);
point[b].push(a);
}
preset();
//cerr << (clock()-start)/1000.0<<endl;
Build(1,n);
m=scan();
for(i=1;i<=n+m-1;i++){
char cc=' ';while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='W'){
a=scan();
printf("%d\n",query(a));
}else{
a=scan();b=scan();
change(a,b);
}
}
//cerr << (clock()-start)/1000.0<<endl;
return 0;
}

题解:
在线:LCT或链剖
离线:树状数组维护欧拉遍历序
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017