POI20填坑计划
感觉是至今推过的最神的一届。。而且还有交互题简直厉害。。
惯例先口胡：
[ByteComputer]：一眼DP
[Tower Defense Game]：直接随便删就好。为了保证复杂度标记哪些点是所连的所有点都被删除的
[Polarization]：详见15年论文“启发式思想”。知道了结论之后就直接背包就好。多重背包我用了倍增+bitset。虽然带个log但是跑的飞起。贪心搞法好神啊。
[Take-out]：直接维护一个栈然后如果最后k+1个可以删除就删除。合法性显然。最后也肯定不会有剩余，这个也可以证明。
[Tales of seafaring]：直接每个点为起点BFS一遍就好
[Taxis]：写个式子很容易发现出租车在左边的时候明显先放大的车更优。于是只要分两种情况：要留一个刚好大于等于右边距离的车和不要留取个答案最大值就好。
[Triumphal arch]：一眼二分答案+树形DP
[Multidrink]：很明显一棵子树只能跳进去一次。然后我觉得树形DP+分类讨论就好。但是分类讨论好麻烦的样子不知道还有没有更加优美的姿势啊。
[Inspector]：二分答案显然，然后我觉得应该就差分搞搞，然后贪心一下就好？Tn log n的
[Walk]：只会在每个点搜一下连通块，然后调下阀值什么的能不能过啊？好虚啊。
[Tapestries]：JB几何题直接弃疗了
[Maze]：这题海瑞斯特说他一眼秒！感觉其实也就是拿个栈维护一下哪些东西可以被提出来，比如LR、RL之类的东西。
[Colorful Chain]：水题。。
[Laser]：波兰文不能看
[Watering can]：水题。。每次删除就好。。
[Watering can]：有点意义不明。。不知道那个M(n)到底是干什么的。。
WC16游记
POI18填坑计划
这个感觉一路都推的比较顺。。只不过经常SB进了细节坑
现在完成了：
16
[Plot]：二分答案显然。。维护凸包的时候顺便查询插入点的对踵点和旁边两个点更新答案就好。。由于只有插入点的动态凸包随便搞就好。。
[Tree Rotations]：SB题。。可以看出每个点的状态对答案的贡献是独立的。。然后就treap启发式合并就好。然后那个什么n log n的treap直接合并可以做这个的加强版吧。。但是treap启发式合并在加强版还是能拿97分所以就没写n log n了。
[Conspiracy]：很容易可以分析出只会有O(n)种答案。而且答案之间最多只会替换一个点。。一堆显然的性质套上去特判就好了。。初始答案只要按度数从大到小取。还要注意特判有一边为空集的情况。
[Lighting Conductor]：一开始以为n*sqrt(n)的RMQ过的去。。后来发现有决策单调性。。然后就直接单调队列维护就好了。。
[Lollipop]：前缀后缀扫一遍。然后发现当1~i的和大于查询数并且第i+1个数为1的时候就可以直接取了。所以排序+扫几遍。
[Temperature]：一个区间是可行的当且仅当不存在i<j使得Li>Rj。归纳法可证。于是就只要单调队列扫一遍就好。。一开始没看空间范围直接上了个线段树MLE。。虽然改一改线段树也是能过的。。
[Strongbox]：先将最后一个数和n gcd一下。然后将得到的这个数和前面的数都gcd一下。然后求n的每个因子可不可以作为答案。并且每个因子可以最多转移到log个节点。
[Garbage]：一眼觉得可以求欧拉回路然后直接算出答案。。但是觉得麻烦就写了一个乱搞结果还是T了。。
[Dynamite]：一开始觉得二分答案+每次找到最深未炸节点炸掉。后面那东西用链表维护是O(n)的。但是还是SB了一下把这样n/Ans次炸这棵树的复杂度算成了O(n)。。= =靠谱做法是DP。。复杂度就是n log n
[Meteors]：整体二分就好。。
[Party]：经典题。讲课讲过很多次。每次选择一个未删除的虚边上两点删掉就好。由于存在团所以肯定有至少一个点不在团上。所以最多删n/3次。。
[Difference]：考虑右端点为k的答案贡献肯定是把最多的算作Ck。然后一路维护前缀和还有Si-Sj的极值即可
[Sticks]：一开始naive不知道为什么觉得要用set。。排个序然后随便维护一下找出最大的异色的前两个棍子。。不知道那个颜色个数小于等于50是怎么用的。。复杂度明显无关的。。
[Inspection]：满足最大子树不超过一半的也就只有重心了吧。。然后直接特判一下最后一步是走最深节点还是只能走其它子树就好了。。
[Programming Contest]：很容易脑补出一个性质：每次Hungary就是最优解。。不会证但是感觉显然。。然后我想了两种写法一种动态删边，一种动态加边。然后作死写了第一种果然有后效性。。两个都是n^3的。。
[Shift]：很容易看出没有解的情况只有n为奇数并且给定状态的逆序对数跟目标状态不同。其余情况我们都可以构造出解。然后我只会n^2次的做法了。。比如每次把一个数往前面提。。比如每次将任意一个三元组变成最优状态（因为每次都会减少一个逆序对所以肯定是n^2的）。。当然感觉上还是前面那个常数会小一些。。我的写法丑了真尼玛调好久。。
[Periodicity]：我记得这题被出到过某ZHZX的NOIP模拟题里面。。简直sxbk。。
数据结构乱做
最近在补课件上一些题目。就只放CLS的一些题目上来好了。。
感觉这些题做起来真是要死。毕竟代码能力弱都要调好久= =做到后面感觉到了深深的绝望。
本来还想开坑Sone1，而且本来想写课件上面给出的LCT套ETT的做法，但是n log^2 n，10w范围，40s时限，常数还这么大。感觉很不资瓷的样子所以写了一半细思之下就退坑了。
BZOJ4068 [CTSC2015] App：首先显然这是个拟阵。然后据说就可以得出一个性质：新加入的任务最多只会替换原来的一个任务。。删除同理，就是这个结论的逆，也就是删除一个任务最多只会加入一个任务到答案中。不管这些东西怎么来之后就是很裸的线段树了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
#define N 300050
#define INF 0x3f7f7f7f
#define fr first
#define sc second
#define ll long long
ll ans;char ch[4];bool b[N];int st,n,m,v[N][2],ne[N];
map <pair <int,int>,int> Ha;
multiset <pair <int,int> > s[N][2];
set <pair <int,int> > :: iterator it;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
struct Segment_Tree
{
int mi[N*4],ad[N*4];pair <int,int> ma[N*4];
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
mi[z]=x;ma[z]=make_pair(-INF,0);
if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
}
inline void adj(int x,int y,int z)
{
int j=z << 1;
if (!ad[z]) return;
if (x!=y) ad[j]+=ad[z],ad[j+1]+=ad[z];
mi[z]+=ad[z];ad[z]=0;
}
inline pair <int,int> Getmax(pair <int,int> x,pair <int,int> y,bool flag)
{return flag?(x.fr<y.fr?y:x):(y.fr<x.fr?x:y);}
inline void Update(int x,int y,int z,bool flag)
{
int j=z << 1;
if (x==y)
{
it=s[x][flag].end();
if (it!=s[x][flag].begin())
ma[z]=*(--it); else
ma[z]=make_pair(-INF,0);
return;
}
mi[z]=min(mi[j],mi[j+1]);ma[z]=Getmax(ma[j],ma[j+1],flag);
}
inline pair <int,int> Trans(int y,bool flag)
{return make_pair(flag?-v[y][1]:v[y][1],y);}
void Delete(int x,int y,int z,int o,int p,bool flag)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y)
{
if (flag) ad[z]=1;
s[x][flag].erase(Trans(p,flag));
adj(x,y,z);Update(x,y,z,flag);return;
}
if (o>i) Delete(i+1,y,j+1,o,p,flag),adj(x,i,j); else
Delete(x,i,j,o,p,flag),
ad[j+1]+=flag?1:0,adj(i+1,y,j+1);
Update(x,y,z,flag);
return;
}
void Insert(int x,int y,int z,int o,int p,bool flag)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y)
{
if (flag) ad[z]=-1;
s[x][flag].insert(Trans(p,flag));
adj(x,y,z);Update(x,y,z,flag);return;
}
if (o>i) Insert(i+1,y,j+1,o,p,flag),adj(x,i,j); else
Insert(x,i,j,o,p,flag),
ad[j+1]+=flag?-1:0,adj(i+1,y,j+1);
Update(x,y,z,flag);
return;
}
pair <int,int> Query(int x,int y,int z,int o,int p,bool flag)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) return ma[z];
if (p<=i) return Query(x,i,j,o,p,flag); else
if (o>i) return Query(i+1,y,j+1,o,p,flag); else
return Getmax(Query(x,i,j,o,i,flag),Query(i+1,y,j+1,i+1,p,flag),flag);
}
int Find_Left(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1,k=0;adj(x,y,z);
if (x==y) return !mi[z]?x:0; else
adj(x,i,j),adj(i+1,y,j+1);
if (!mi[j]&&o<=i) k=Find_Left(x,i,j,o);
if (!k&&!mi[j+1]) k=Find_Left(i+1,y,j+1,max(o,i+1));
return k;
}
int Find_Right(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y) return !mi[z]?x:0; else
adj(x,i,j),adj(i+1,y,j+1);
if (!mi[j+1]) return Find_Right(i+1,y,j+1); else
return Find_Right(x,i,j);
}
} A,B;
void Delete(int x,int y)
{
int sg=Ha[make_pair(x,y)];
Ha[make_pair(x,y)]=ne[sg];
if (!b[sg]) {B.Delete(1,n,1,x,sg,false);return;}
A.Delete(1,n,1,x,sg,true);int k=A.Find_Right(1,n,1);
k=B.Query(1,n,1,k+1,n,false).sc;ans-=y;b[sg]=false;
if (k)
B.Delete(1,n,1,v[k][0],k,false),
A.Insert(1,n,1,v[k][0],k,true),
ans+=v[k][1],b[k]=true;
return;
}
void Insert(int x,int y)
{
v[++st][0]=x;v[st][1]=y;
ne[st]=Ha[make_pair(x,y)];Ha[make_pair(x,y)]=st;
int k=A.Find_Left(1,n,1,x);
if (!k&&y>=0)
{A.Insert(1,n,1,x,st,true);b[st]=true;ans+=y;return;}
k=A.Query(1,n,1,1,k,true).sc;
if (v[k][1]>=y) B.Insert(1,n,1,x,st,false); else
{
A.Delete(1,n,1,v[k][0],k,true);b[k]=false;
B.Insert(1,n,1,v[k][0],k,false);
A.Insert(1,n,1,x,st,true);b[st]=true;
ans+=y-v[k][1];
}
return;
}
int main()
{
n=Read();m=Read();A.Set_up(1,n,1);B.Set_up(1,n,1);
for (int i=1;i<=m;i++)
{
int k,l;scanf("%s%d%d",ch,&k,&l);
if (ch[0]=='D') Delete(k,l); else Insert(k,l);
printf("%lld\n",ans);
}
return 0;
}
BZOJ3435 [WC2014]紫荆花之恋：经典题，替罪羊树套点分治套treap。因为替罪羊维持平衡的部分出了些微妙的错误导致TLE一直都没看出来= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;
#define N 100050
#define M 6000050
#define P 4000050
#define INF (int)1e9
#define eps 0.78
#define ll long long
int c[N*2][3],h[N],dep[N],r[N],li[N],n,m,ss=1;
ll ans;int dis[N][30],fi[N],Dis[N];bool Flag;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;c[ss][2]=z;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;c[ss][2]=z;
}
struct Node
{
Node *c[2];int v,s,val;
} used[P],*unused[P],*pool = used,**top = unused,*rt[N][2],Emp,*emp=&Emp;
struct Balance_Tree
{
inline Node* Get(int x)
{
Node *k = (top != unused) ? *--top : pool++;
k->c[0]=k->c[1]=emp;
k->s=1;k->v=x;k->val=rand();
return k;
}
inline void Update(Node *x)
{x->s=x->c[0]->s+x->c[1]->s+1;}
void Rotate(Node* &x,Node* y)
{
bool k=y==x->c[0];
x->c[!k]=y->c[k];y->c[k]=x;
y->s=x->s;Update(x);x=y;
return;
}
void Insert(Node* &x,Node* y)
{
bool flag=y->v>x->v;
if (x==emp) {x=y;return;} else x->s++;
Insert(x->c[flag],y);
if (x->c[flag]->val>x->val)
Rotate(x,x->c[flag]);
return;
}
int Query(Node* x,int y)
{
if (x==emp) return 0;
if (y>=x->v) return x->c[0]->s+1+Query(x->c[1],y); else
return Query(x->c[0],y);
}
void Clear(Node* &x)
{
if (x==emp) return;
*top++ = x;
Clear(x->c[0]);Clear(x->c[1]);
x=emp;
}
Node* Rebuild(int x,int y)
{
Node* Rt=Get(dis[li[1]][y]-r[li[1]]);
for (int i=2;i<=x;i++)
Insert(Rt,Get(dis[li[i]][y]-r[li[i]]));
return Rt;
}
} B;
struct Divide_Tree
{
int suf[N],cnt[N],sg[N],sz[N],Rt,Sg;
int Get_Size(int x)
{
int le=1,ri=1;li[1]=x;sz[x]=-1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!sz[c[i][0]]&&!sg[c[i][0]])
sz[li[++ri]=c[i][0]]=-1;
return ri;
}
int Get_Rt(int Cnt)
{
int Ctr=li[1];
for (int i=Cnt;i>=1;i--)
{
sz[li[i]]=1;
for (int j=fi[li[i]];j;j=c[j][1])
if (!sg[c[j][0]]&&sz[c[j][0]]>0) sz[li[i]]+=sz[c[j][0]];
}
while (true)
{
bool flag=false;
for (int i=fi[Ctr];i;i=c[i][1])
if (sz[c[i][0]]<sz[Ctr]&&!sg[c[i][0]]&&sz[c[i][0]]*2>=Cnt)
{Ctr=c[i][0];flag=true;break;}
if (!flag) break;
}
for (int i=1;i<=Cnt;i++) sz[li[i]]=0;
return Ctr;
}
void DFS(int x,int y,int z)
{
for (int i=fi[x];i;i=c[i][1])
if (!sg[c[i][0]]&&c[i][0]!=y)
dis[c[i][0]][z]=dis[x][z]+c[i][2],
DFS(c[i][0],x,z);
return;
}
void Rebuild(int x,int y,int z)
{
int Cnt=Get_Size(x),Ctr=Get_Rt(Cnt);
dis[Ctr][y]=0;DFS(Ctr,0,y);sg[Ctr]=y;
if (z) suf[Ctr]=z; else
suf[Rt=Ctr]=0,rt[Ctr][1]=emp;
rt[Ctr][0]=B.Rebuild(Cnt,y);cnt[Ctr]=Cnt;
if (y>1) rt[Ctr][1]=B.Rebuild(Cnt,y-1);
for (int i=fi[Ctr];i;i=c[i][1])
if (!sg[c[i][0]]) Rebuild(c[i][0],y+1,Ctr);
return;
}
void Clear(int x)
{
if (!sg[x]||sg[x]<Sg) return;sg[x]=0;
B.Clear(rt[x][0]);B.Clear(rt[x][1]);
for (int i=fi[x];i;i=c[i][1]) Clear(c[i][0]);
}
void Get(int x,int y)
{
cnt[x]=1;sg[x]=sg[suf[x]]+1;int ma=0;
rt[x][0]=B.Get(-y);rt[x][1]=B.Get(c[ss][2]-y);
memcpy(dis[x],dis[suf[x]],sizeof dis[suf[x]]);
for (int i=1;i<sg[x];i++) dis[x][i]+=c[ss][2];
dis[x][sg[x]]=0;
for (int i=suf[x],j=sg[x]-1;i;i=suf[i],j--)
{
cnt[i]++;
if (j-1&&cnt[i]/(cnt[suf[i]]+1.0)>eps) ma=suf[i];
ans+=B.Query(rt[i][0],y-dis[x][j]);
B.Insert(rt[i][0],B.Get(dis[x][j]-y));
if (j-1)
ans-=B.Query(rt[i][1],y-dis[x][j-1]),
B.Insert(rt[i][1],B.Get(dis[x][j-1]-y));
}
if (ma)
Sg=sg[ma],Clear(ma),Rebuild(ma,Sg,suf[ma]);
return;
}
} A;
int main()
{
Read();n=Read();Read();Read();
A.Rt=1;Emp.c[0]=Emp.c[1]=&Emp;
srand(23335900);//Orz TATQAQ2333 and yyh5900
A.Get(1,r[1]=Read());puts("0");
for (int i=2;i<=n;i++)
{
int q=Read()^(ans%INF),w=Read();r[i]=Read();
h[i]=h[q]+1;dep[i]=dep[q]+w;
Line(i,q,w);A.suf[i]=q;
A.Get(i,r[i]);printf("%lld\n",ans);
}
return 0;
}
BZOJ3068 小白树：直接枚举断边就好。然后答案就是分成的两棵树的重心。至于为什么因为每种方案都对应了至少一个断边，然而每种断边的最优解又肯定是在两棵树重心处。所以虽然不一定一个两棵树的重心的断边一定是枚举的那个但是这种方案肯定是比其它断边为这条的方案更优的。所以就只要求出一个东西：一棵子树的重心和对应答案是什么。去掉这棵子树的重心和对应答案是什么。前面那个东西很好求，只需要求出一个点每棵子树的答案然后再找出自身的重心在哪棵子树，然后暴力往上移动就好。这种方法类似于启发式合并，复杂度也是一样。至于求一棵子树的补的重心，我们考虑二分答案。首先设去掉的子树的父亲是i，那么如果在i的某棵子树内，就肯定是在这棵子树的重心和i的连线上。如果是在i的上面，就肯定在fai的重心和i的连线上。于是二分答案然后通过子树重量判断就好。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500050
#define M 19
#define ll long long
int fa[N][M],h[N],ma[N][2],v[N],fi[N],c[N*2][2],li[N],n,m,ss=1;
ll cnt[N][2],Ans[N][2],Cnt[N],ans,Aha;int la[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void Get()
{
int le=1,ri=1;li[1]=1;h[1]=1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (c[i][0]!=fa[li[le]][0])
fa[c[i][0]][0]=li[le],h[li[++ri]=c[i][0]]=h[li[le]]+1;
return;
}
void DFS()
{
for (int t=n;t>=1;t--) {
int x=li[t];cnt[x][0]=v[x];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
{
cnt[x][0]+=cnt[c[i][0]][0];
cnt[x][1]+=cnt[c[i][0]][0]+cnt[c[i][0]][1];
if (cnt[c[i][0]][0]>=cnt[ma[x][0]][0])
ma[x][1]=ma[x][0],ma[x][0]=c[i][0]; else
if (cnt[c[i][0]][0]>=cnt[ma[x][1]][0])
ma[x][1]=c[i][0];
}
if (ma[x][0]&&cnt[ma[x][0]][0]*2>=cnt[x][0])
{
Ans[x][0]=Ans[ma[x][0]][0];
Ans[x][1]=Ans[ma[x][0]][1]+cnt[x][1]-cnt[ma[x][0]][1]-
cnt[ma[x][0]][0]+(cnt[x][0]-cnt[ma[x][0]][0])*
(h[Ans[x][0]]-h[x]);
while (cnt[Ans[x][0]][0]*2<cnt[x][0])
Ans[x][1]+=2*cnt[Ans[x][0]][0]-cnt[x][0],
Ans[x][0]=fa[Ans[x][0]][0];
} else Ans[x][0]=x,Ans[x][1]=cnt[x][1];
}
return;
}
inline ll min(ll x,ll y)
{return x<y?x:y;}
void DSF()
{
for (int t=1;t<=n;t++) {
int x=li[t];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
Cnt[c[i][0]]=Cnt[x]-2*cnt[c[i][0]][0]+Aha;
}
return;
}
int LCA(int x,int y)
{
if (h[x]<h[y]) swap(x,y);
for (int i=M-1;i>=0;i--)
if (h[fa[x][i]]>=h[y]) x=fa[x][i];
if (x!=y)
{
for (int i=M-1;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
x=fa[x][0];
}
return x;
}
int Up(int x,int y,ll z,ll o)
{
if (x!=y&&(cnt[x][0]+o)*2>=z) return x;
for (int i=M-1;i>=0;i--)
if (fa[x][i]&&(cnt[fa[x][i]][0]+o)*2<z) x=fa[x][i];
return h[x]-1>h[y]?fa[x][0]:0;
}
void DFF()
{
for (int t=1;t<=n;t++) {
int x=li[t],y=la[x];
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
{
ll k=Aha-cnt[c[i][0]][0],l=0,Tot=0;int e=0;
if ((Aha-cnt[x][0])*2>=k) l=-1; else
if (cnt[ma[x][0]][0]*2>=k&&ma[x][0]!=c[i][0])
l=ma[x][0]; else
if (ma[x][1]&&cnt[ma[x][1]][0]*2>=k&&
ma[x][1]!=c[i][0]) l=ma[x][1];
if (!l)
e=x,Tot=Cnt[x]-cnt[c[i][0]][1]-cnt[c[i][0]][0]; else
if (l>0)
e=Up(Ans[l][0],x,k,0),
Tot=Cnt[e]-cnt[c[i][0]][1]-
cnt[c[i][0]][0]*(1+h[e]-h[x]); else
{
l=LCA(y,x);ll tot=0;e=Up(y,l,k,0);
if (!e)
e=Up(x,fa[l][0],k,-cnt[c[i][0]][0]),
Tot=Cnt[e]-cnt[c[i][0]][1]-cnt[c[i][0]][0]*
(h[c[i][0]]-h[e]); else
Tot=Cnt[e]-cnt[c[i][0]][1]-cnt[c[i][0]][0]*
(h[e]+h[c[i][0]]-2*h[l]);
}
ans=min(ans,Tot+Ans[c[i][0]][1]);
la[c[i][0]]=e;
}
}
return;
}
void Solve()
{
Get();DFS();
for (int i=1;i<M;i++)
for (int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
Cnt[1]=cnt[1][1];DSF();DFF();
return;
}
int main()
{
n=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
for (int i=1;i<=n;i++) Aha+=(v[i]=Read());
ans=1LL << 60;Solve();
cout <<ans<<endl;
return 0;
}
HDU5574 [ACM 2015 Shanghai]：Colorful Tree
DFS序建线段树，两棵线段树分别维护答案和标记个数。设一个点的颜色为它上面第一个标记的颜色。每次相当于添加一个标记以及将子树内所有标记删除。于是考虑删除一个标记对答案的影响：如果子树内还有同色标记无影响，否则其直到与其DFS序相邻的两个标记的最深LCA的路径上面的答案-1，这东西树剖维护即可。添加标记同理，只不过子树内所有点答案赋为1。复杂度两个log。课件上面这么写的。。后来写了之后才发现只考虑最近的两个标记是有问题的。如果一个点祖先也有同色标记，那么标记下面到修改点的路径上面就会答案加一。但其实是最深同色点到修改点的路径上面答案加一。同时还要考虑DFS序相邻的两个点。所以应该修改的路径应该是原来求的东西和最深祖先同色点中的最深点，这东西用set维护一下就好。这部分复杂度也是两个log。我的写法应该是最丑的吧。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
int rf[N],c[N*2][2],fa[N],fi[N],mark[N],li[N],sg[N][2],h[N];
int ms[N*4],cs[N*4],ad[N*4],s[N],v[N],n,m,ss,st,t;bool xg[N*4];
multiset <int> ne[N],Mark;bool Flag;
set <int> :: iterator it;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x]=h[fa[x]]+1;s[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),s[x]+=s[c[i][0]];
return;
}
void DSF(int x,int y)
{
rf[x]=y;int k=0;li[sg[x][0]=++st]=x;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&s[c[i][0]]>s[k]) k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k) DSF(c[i][0],c[i][0]);
sg[x][1]=st;
return;
}
inline void xgj(int x,int y,int z)
{
int j=z << 1;
if (!xg[z]) return;
if (x!=y)
for (int i=0;i<2;i++)
ad[j+i]=false,xg[j+i]=true; else cs[z]=1;
xg[z]=false;return;
}
inline void adj(int x,int y,int z)
{
int j=z << 1;
if (!ad[z]) return;
if (x!=y)
ad[j]+=ad[z],ad[j+1]+=ad[z]; else cs[z]+=ad[z];
ad[z]=0;return;
}
int Query(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;
xgj(x,y,z);adj(x,y,z);
if (x==y) return cs[z];
if (o<=i) return Query(x,i,j,o); else
return Query(i+1,y,j+1,o);
}
void Insert(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;ms[z]++;
if (x==y) return;
if (o<=i) Insert(x,i,j,o); else Insert(i+1,y,j+1,o);
return;
}
void Add(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=z << 1;
xgj(x,y,z);adj(x,y,z);
if (x==o&&y==p) {ad[z]=u;adj(x,y,z);return;}
if (p<=i) Add(x,i,j,o,p,u); else
if (o>i) Add(i+1,y,j+1,o,p,u); else
Add(x,i,j,o,i,u),Add(i+1,y,j+1,i+1,p,u);
return;
}
void Modify(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
xgj(x,y,z);adj(x,y,z);
if (x==o&&y==p) {xg[z]=true;xgj(x,y,z);return;}
if (p<=i) Modify(x,i,j,o,p); else
if (o>i) Modify(i+1,y,j+1,o,p); else
Modify(x,i,j,o,i),Modify(i+1,y,j+1,i+1,p);
return;
}
void Increase(int x,int y,int z)
{
while (rf[x]!=rf[y])
Add(1,n,1,sg[rf[x]][0],sg[x][0],z),x=fa[rf[x]];
Add(1,n,1,sg[y][0],sg[x][0],z);
return;
}
int LCA(int x,int y)
{
int lx=0;
while (rf[x]!=rf[y])
{
bool flag=false;
if (h[rf[y]]>h[rf[x]]) swap(x,y),flag=true;
x=rf[x];if (!flag) lx=x;x=fa[x];
if (flag) swap(x,y);
}
if (h[x]<=h[y]) return lx; else return li[sg[y][0]+1];
}
inline int Lower(int x,int y)
{return x==-1||h[x]<h[y]?y:x;}
int Get(int x,int y)
{
int k=-1,l=x,e;
while (l)
{
it=ne[y].lower_bound(sg[l][0]+1);
if (it!=ne[y].begin())
if (*(--it)!=sg[x][0]) it++;
if (it!=ne[y].begin()&&(*(--it)>=sg[rf[l]][0]))
{k=li[*it];break;}
l=fa[rf[l]];
}
if (k==-1) return k;l=e=x;
while (l)
{
it=Mark.lower_bound(rf[l]==rf[k]?sg[k][0]+1:sg[rf[l]][0]);
if (it!=Mark.end()&&*it<=sg[l][0]) e=li[*it];
if (rf[l]==rf[k]) break;
l=fa[rf[l]];
}
return e;
}
void Pop(int x,int y)
{
if (!mark[x]) return;
Mark.erase(sg[x][0]);int k=Get(x,y);
it=ne[y].lower_bound(sg[x][0]);
if (it!=ne[y].begin()) k=Lower(k,LCA(x,li[*(--it)])),it++;
if (++it!=ne[y].end())
{
int l=*it;
if (sg[li[l]][1]<=sg[x][1]) {it--;ne[y].erase(it);return;}
k=Lower(k,LCA(x,li[l]));
}
it--;ne[y].erase(it);
Increase(x,k==-1?1:k,-1);
return;
}
void Push(int x,int y)
{
Insert(1,n,1,sg[x][0]);ne[y].insert(sg[x][0]);
int k=Get(x,y);Mark.insert(sg[x][0]);
it=ne[y].lower_bound(sg[x][0]);
if (it!=ne[y].begin()) k=Lower(k,LCA(x,li[*(--it)])),it++;
if (++it!=ne[y].end())
{
int l=*it;
if (sg[li[l]][1]<=sg[x][1]) return;
k=Lower(k,LCA(x,li[l]));
}
Increase(x,k==-1?1:k,1);
return;
}
void Delete(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (!ms[z]) return;
if (x==y) {Pop(li[x],mark[li[x]]);mark[li[x]]=ms[z]=0;return;}
if (p<=i) Delete(x,i,j,o,p); else
if (o>i) Delete(i+1,y,j+1,o,p); else
Delete(x,i,j,o,i),Delete(i+1,y,j+1,i+1,p);
ms[z]=ms[j]+ms[j+1];
return;
}
void Gay_a_wave(int y,int x)
{
Delete(1,n,1,sg[x][0],sg[x][1]);
Push(x,y);mark[x]=y;Modify(1,n,1,sg[x][0],sg[x][1]);
}
void Pretreat()
{
DFS(1);DSF(1,1);
for (int i=1;i<=n;i++) Gay_a_wave(v[li[i]],li[i]);
return;
}
void Clear(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
cs[z]=ms[z]=xg[z]=ad[z]=false;
if (x!=y) Clear(x,i,j),Clear(i+1,y,j+1);
}
int main()
{
t=Read();
for (int T=1;T<=t;T++)
{
printf("Case #%d:\n",T);
n=Read();ss=1;st=0;
for (int i=1;i<n;i++) Line(Read(),Read());
for (int i=1;i<=n;i++) v[i]=Read();
Pretreat();m=Read();Flag=true;
for (int i=1;i<=m;i++)
if (Read())
printf("%d\n",Query(1,n,1,sg[Read()][0])); else
Gay_a_wave(Read(),Read());
for (int i=1;i<=n;i++)
fi[i]=mark[i]=false,ne[i].clear();
Mark.clear();Clear(1,n,1);
}
return 0;
}
BZOJ2957
之前不知为何记得这个是树套树好题于是抽空做了一下。思索很久无果。
感觉倒是线段树还有分块做法一下就想出来了。。（其实线段树做法是因为刚好做过一道差不多的题才会做= =）
线段树做法很优美啊：
维护每段区间的答案。还有这个答案的右端点。
Update的时候套个询问就好了。具体可以看这里。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
double bd[N*4];int Ans[N*4],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline double max(double x,double y)
{return x<y?y:x;}
int Query(int x,int y,int z,double o)
{
int i=x + y >> 1,j=z << 1;
if (x==y) return bd[z]>o;
if (bd[j]<=o) return Query(i+1,y,j+1,o); else
return Ans[z]-Ans[j]+Query(x,i,j,o);
}
void Modify(int x,int y,int z,int o,double p)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {Ans[z]=1;bd[z]=p;return;}
if (o<=i) Modify(x,i,j,o,p); else
Modify(i+1,y,j+1,o,p);
bd[z]=max(bd[j],bd[j+1]);
Ans[z]=Ans[j]+Query(i+1,y,j+1,bd[j]);
return;
}
int main()
{
n=Read();m=Read();
while (m--)
{
int k=Read(),l=Read();Modify(1,n,1,k,l*1.0/k);
printf("%d\n",Ans[1]);
}
return 0;
}
