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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3531][Sdoi2014]旅行  

2014-12-06 19:10:31|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3531: [Sdoi2014]旅行

今年省选题
当时做的时候啥也不会QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
typedef int ll;
int n,m,T;
int dc[N],dw[N];
struct Node{
Node();
int d,best;short flag;
ll size;
Node *ch[2],*fa;
short pl(){return this == fa->ch[1];}
void count();void push();
}point[N],*null;
Node::Node(){ch[0] = ch[1] = fa = null;flag = d = size = best = 0;}
void Node::push(){
if(this == null)return;
if(flag){
swap(ch[0],ch[1]);
ch[0]->flag^=1;
ch[1]->flag^=1;
flag=0;
}
}
void Node::count(){
if(this == null)return;
size = ch[0]->size + ch[1]->size + d;
best = d;
best = max(best,ch[0]->best);
best = max(best,ch[1]->best);
}
struct LCT{
LCT(){
null = new Node;
*null = Node();
}
bool notr(Node *r){return r==r->fa->ch[0] || r==r->fa->ch[1];}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==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->pl()==r->fa->pl()?r->fa:r);
r->push();
}
Node *root(Node *r){
hello(r);splay(r);
while(r->ch[0]!=null)r = r->ch[0];
return r;
}
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;
}
void changer(Node *r){
hello(r)->flag^=1;
//printf("Changer\n");
splay(r);
}
void link(Node *r,Node *l){
changer(r);r->fa = l;
hello(r);
}
void cut(Node *r, Node *l){
changer(r);
hello(l);splay(l);
l->ch[0] = r->fa = null;
l->count();//*
}
Node *ask(Node *r,Node *l){
changer(r);
hello(l);
splay(l);
return l;
}
void add(Node *r,int val){
changer(r);
r->d += val;
if(r->d < 0)r->d = 0;
r->count();
}
void clear(Node *r){
changer(r);
r->d = 0;
r->count();
}
}lt;
//t: 0:add 1:AskSum 2:AskMax
struct Data{
int r,i,t,c,d;
Data(){}
Data(int rank,int ii,int type,int cc,int dd):r(rank),i(ii),t(type),c(cc),d(dd){}
void print(){
printf("%d %d %d C:%d D:%d\n",r,i,t,c,d);
}
}ask[N*5];int an;
ll ans[N*5];
bool Ask_Cmp(Data a,Data b){
if(a.c!=b.c)return a.c < b.c;
if(a.r!=b.r)return a.r < b.r;
return a.i < b.i;
}
bool operator == (Data a,Data b){return a.t==0 && b.t==0 && a.r>=1e9 && a.r==b.r && a.i==b.i;}
//int scan(){int i=0;scanf("%d",&i);return i;}
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;
}
char Output[N*10];int end;
void print(int x,short type=0){
if(x >= 10)print(x/10,1);
Output[end++] = x%10+'0';
if(!type)Output[end++] = '\n';
}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b;
n = scan();m = scan();
for(i=1;i<=n;i++){
point[i] = Node();
dw[i] = a = scan();
dc[i] = b = scan();
ask[++an] = Data(0,i,0,b,a);
ask[++an] = Data(1e9,i,0,b,-a);
}
for(i=1;i<n;i++){

a = scan();b = scan();
//printf("%d %d\n",a,b);
lt.link(&point[a],&point[b]);
}
char cc[10];
for(i=1;i<=m;i++){
scanf("%s",cc);
a = scan();b = scan();
//Change
if(cc[0]=='C'&&cc[1]=='C')
ask[++an] = Data(++T,a,0,dc[a],-dw[a]),
ask[++an] = Data(++T,a,0,(dc[a]=b),dw[a]),
ask[++an] = Data(1e9,a,0,dc[a],-dw[a]);
if(cc[0]=='C'&&cc[1]=='W')
ask[++an] = Data(++T,a,0,dc[a],b-dw[a]),dw[a]=b;
//Ask
if(cc[0]=='Q'&&cc[1]=='S')ask[++an] = Data(++T,a,1,dc[a],b);
if(cc[0]=='Q'&&cc[1]=='M')ask[++an] = Data(++T,a,2,dc[a],b);
//printf("%s\n",cc);
}
sort(ask+1,ask+1+an,Ask_Cmp);
an = unique(ask+1,ask+1+an) - ask - 1;
for(i=1;i<=an;i++){
//printf("[%d]\n",i);
//ask[i].print();
if(!ask[i].t){
if(ask[i].r < 1e9)lt.add(&point[ask[i].i],ask[i].d);
else lt.clear(&point[ask[i].i]);
}else{
Node *r = lt.ask(&point[ask[i].i],&point[ask[i].d]);
if(ask[i].t==1)ans[ask[i].r] = r->size;
if(ask[i].t==2)ans[ask[i].r] = r->best;
//printf("ans:%d\n",ans[ask[i].r]);
}
}
for(i=1;i<=T;i++)
if(ans[i])print(ans[i]);
Output[end] = 0;
puts(Output);
return 0;
}


题解:
比较经典的思路,离线之后按照颜色排序搞。
LCT或者是链剖线段树都行。
个人感觉LCT比较短就写了LCT

一开始因为清0的地方写的是减去xxx而不是等于0,导致各种奇怪的地方出现问题,WA了好久= =、果然还是老老实实写=0吧。

  评论这张
 
阅读(69)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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