文档章节

洛谷P3613 睡觉困难综合征

o
 osc_1ee7cxmx
发布于 2018/08/06 16:27
字数 1369
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

传送门

题解

人生第一道由乃……

做这题之前应该先去把这一题给切掉->这里

我的题解->这里

然后先膜一波zsy大佬和flashhu大佬

大体思路就是先吧全0和全1的都跑答案,然后按位贪心

我一开始想到的是每一次split,然后直接一个一个跑

后来发现时间复杂度肯定爆炸……

看了看网上其他的,发现说的都不怎么清楚……结果硬是理解了好久才明白……

先考虑一下LCT维护什么

定义$f0$为全0走过一条路径之后的答案,$f1$表示全1走过一条路径之后的答案

LCT需要维护的是splay中以x为根的子树里,从前往后遍历(即中序遍历)的$f0$和$f1$以及从后往前(即与前面完全相反的顺序)的$f0$和$f1$

比如有一棵splay,x是其中一个点,它在splay中有两个儿子,左儿子y和右儿子z,那么从前往后遍历就是路径y->x->z,从后往前就是路径z->x->y

然后思考,如果已经有了两个区间,该如何合并他们

假如说我们有两段计算出答案的区间,分别对应f0,f1和g0,g1。我们设合并后的答案是h0,h1,那么有如下式子:

$h0=(~f0&g0)+(f0&g1)$

$h1=(~f1&g0)+(f1&g1)$

为啥?

全0走到最后的话,先考虑两种情况

全0走到中间等于1的那几位,走后一半的答案等同于全1走后一半的这几位的答案

全0走到中间等于0的那几位,走后一半的答案等同于全0走后一半的这几位的答案

只需要把这两个答案加起来即可

(ps:这里默认f为前一半的答案,g为后一半的答案)

全1走到最后同理

然后就是几个细节

1.pushdown的时候因为有翻转标记,从前往后走和从后往前走的答案也要交换

2.按位贪心用1做位运算的时候,记得把1设成unsigned long long(简单来说就是设一个ull变量让它等于1)(我就是因为一开始直接用1做位运算结果死都调不出来……)

  1 // luogu-judger-enable-o2
  2 //minamoto
  3 #include<iostream>
  4 #include<cstdio>
  5 #define ll unsigned long long
  6 using std::swap;
  7 using std::cout;
  8 using std::endl;
  9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 10 char buf[1<<21],*p1=buf,*p2=buf;
 11 inline ll read(){
 12     #define num ch-'0'
 13     char ch;bool flag=0;ll res;
 14     while(!isdigit(ch=getc()))
 15     (ch=='-')&&(flag=true);
 16     for(res=num;isdigit(ch=getc());res=res*10+num);
 17     (flag)&&(res=-res);
 18     #undef num
 19     return res;
 20 }
 21 char obuf[1<<24],*o=obuf;
 22 void print(ll x){
 23     if(x>9) print(x/10);
 24     *o++=x%10+48;
 25 }
 26 const int N=100005;
 27 struct node{
 28     ll f0,f1;
 29     inline node operator +(const node &b)const
 30     {
 31         node a;
 32         a.f0=(~f0&b.f0)|(f0&b.f1);
 33         a.f1=(~f1&b.f0)|(f1&b.f1);
 34         return a;
 35     }
 36 }f[N],l[N],r[N];
 37 int fa[N],ch[N][2],s[N],rev[N],top,tot;
 38 int ver[N<<1],head[N],Next[N<<1];
 39 inline void add(int u,int v){
 40     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
 41     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
 42 }
 43 inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
 44 #define ls ch[x][0]
 45 #define rs ch[x][1]
 46 inline void pushup(int x){
 47     l[x]=r[x]=f[x];
 48     if(ls) l[x]=l[ls]+l[x],r[x]=r[x]+r[ls];
 49     if(rs) l[x]=l[x]+l[rs],r[x]=r[rs]+r[x];
 50 }
 51 inline void pushr(int x){
 52     swap(ls,rs),swap(l[x],r[x]),rev[x]^=1;
 53 }
 54 inline void pushdown(int x){
 55     if(rev[x]&&x){
 56         pushr(ls),pushr(rs),rev[x]=0;
 57     }
 58 }
 59 void rotate(int x){
 60     int y=fa[x],z=fa[y],d=ch[y][1]==x;
 61     if(!isroot(y)) ch[z][ch[z][1]==y]=x;
 62     fa[x]=z,fa[y]=x,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y,pushup(y);
 63 }
 64 void splay(int x){
 65     s[top=1]=x;for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];
 66     while(top) pushdown(s[top--]);
 67     for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){
 68         if(!isroot(y))
 69         ((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y);
 70         rotate(x);
 71     }
 72     pushup(x);
 73 }
 74 void access(int x){
 75     for(int y=0;x;x=fa[y=x]){
 76         splay(x),rs=y,pushup(x);
 77     }
 78 }
 79 void makeroot(int x){
 80     access(x),splay(x),pushr(x);
 81 }
 82 void split(int x,int y){
 83     makeroot(x),access(y),splay(y);
 84 }
 85 void dfs(int u){
 86     for(int i=head[u];i;i=Next[i]){
 87         int v=ver[i];
 88         if(v==fa[u]) continue;
 89         fa[v]=u,dfs(v);
 90     }
 91     pushup(u);
 92 }
 93 int main(){
 94     //freopen("testdata.in","r",stdin);
 95     int n=read(),m=read(),k=read();
 96     for(int i=1;i<=n;++i){
 97         int x=read();ll y=read();
 98         switch(x){
 99             case 1:f[i]=(node){0,y};break;
100             case 2:f[i]=(node){y,~0};break;
101             case 3:f[i]=(node){y,~y};break;
102         }
103     }
104     for(int i=1;i<n;++i){
105         int u=read(),v=read();add(u,v);
106     }
107     dfs(1);
108     while(m--){
109         int opt=read(),x=read(),y=read();ll z=read();
110         if(opt&1){
111             split(x,y);ll ans=0,e=1;
112             for(int i=k-1;i>=0;--i){
113                 if(l[y].f0&(e<<i)) ans|=e<<i;
114                 else if((l[y].f1&(e<<i))&&z>=(e<<i)) ans|=e<<i,z^=e<<i;
115             }
116             print(ans),*o++='\n';
117         }
118         else{
119             switch(y){
120                 case 1:f[x]=(node){0,z};break;
121                 case 2:f[x]=(node){z,~0};break;
122                 case 3:f[x]=(node){z,~z};break;
123             }
124             splay(x);
125         }
126     }
127     fwrite(obuf,o-obuf,1,stdout);
128     return 0;
129 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

强制行家更新 - Force maven update

问题: I imported my working project on other computer so it started to download dependencies. 我将工作项目导入其他计算机,因此它开始下载依赖项。 Apparently in the meantime my ......

javail
35分钟前
13
0
skywalking实现分布式系统链路追踪

一、背景 随着微服务的越来越流行,我们服务之间的调用关系就显得越来越复杂,我们急需一个APM工具来分析系统中存在的各种性能指标问题以及调用关系。目前主流的APM工具有CAT、Zipkin、Pinpo...

燚-焱
42分钟前
16
0
2020最新的Spring Boot 分布式锁的具体实现(内附代码)

前言 面试总是会被问到有没有用过分布式锁、redis 锁,大部分读者平时很少接触到,所以只能很无奈的回答 “没有”。本文通过 Spring Boot 整合 redisson 来实现分布式锁,并结合 demo 测试结...

北柠Java
48分钟前
28
0
Shiro中获取Cookie

自定义shiro的SessionIdCookie 在使用shiro的时候,曾经有段时间很苦恼,因为我cookie的sessionId经常无故被改,然后抛There is no session with id [xxxx]的异常。我们知道,当请求过来,s...

豫华商
48分钟前
14
0
JPA和Hibernate有什么区别? [关闭] - What's the difference between JPA and Hibernate? [closed]

问题: I understand that JPA 2 is a specification and Hibernate is a tool for ORM. 我知道JPA 2是一个规范,而Hibernate是ORM的工具。 Also, I understand that Hibernate has more fea......

富含淀粉
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部