Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 线段树 /* http://acm.cug.edu.cn/problem.php?cid=1176&pid=1 */ // 区间赋值为0/1,区间的值取反 //线段树动态开点 // 区间翻转0/1+区间赋值0/1+区间求和的双标记动态开点线段树.html #define ml ((l+r)>>1) #define mr (ml+1) const int maxn=5e4+5; int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot; void push_son(int&son,int l,int r,int covrt,int ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 吉司机线段树 hdu5306 #define ml ((l+r)>>1) #define mr (ml+1) #define ls (rt<<1) #define rs (ls|1) int mx1[maxn<<2],num[maxn<<2],mx2[maxn<<2],lz[maxn<<2],a[maxn]; long long sum[maxn<<2]; void push_son(int son,int l,int r,int lzrt){//把最大值变为lzrt ，次大值不变 if(lzrt<mx1[son]){ sum[son]-=1ll*(mx1[so ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 一维树状数组 笔者眼中的一维树状数组         一维树状数组，是一棵左偏树，他的每一个节点，维护的是一段区间的和,若该节点的 下标为i，那么他维护的区间就是(i&(i-1),i] ，熟悉位运算的人应该都知道，i&(i-1)与i的关系：i&(i-1)和i去掉i的二进制中的最低位的1后的值 相等。并且，树状数组就是做单点修改，前缀区间查询的数据结构。 为了利 于描述，下文暂时称一维树状数组为树状数组 树状数组询问操作         原数组的前缀 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 树链剖分        如果给出一棵树并为每个节点标号1234...n;并定义区间[x,y]为树上节点x到节点y的最短路所经过的所有节点组成的集合，注意是闭区间，包括x，y两个节点              树链剖分能够解决树上区间的操作，是线段树功能的强化版，但他也依赖着线段树。        树链剖分尝试着把树分割为多条链，并按照dfs序对链排序并交给线段 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 线段树 线段树         线段树是树状数组的强化版，它每次对区间进行二分，每一个深度都维护了整个区间，在同一深度里面，每个节点维护的区间长度大致相同，而每深入一层又大致比上一层多一倍的节点，故空间复杂度为Onlgn 节点信息         每个非叶子节点维护一个区间[l,r]，令mid=(l+r)>>1,则该节点的左儿子维护[l,mid]，右儿子维护[mid+1,r]；         每个叶子 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 线段树套线段树 我的第一颗树套树        树套树的思路估计都这样子了，树套树分为外树和内树，也可以分为第一维树和 第二维树，我这里把他们叫做x树和y树，即x树为外树，y树为内树。我们描述时 用内外，代码用xy。        首先树套树，顾名思义，给出定义，树套树是一棵节点是树的树 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog 镜像并查集 镜像处理时都有这种关系 朋友的朋友是朋友，敌人的敌人是朋友，朋友的敌人是敌人，敌人的朋友是朋友， 如何快速判断朋友与敌人呢？ 我们让每个人都有两重身份，一个是自己，一个是自己的相反面，即a与a'是天生的敌人，b与b'是天生的敌人 当a和b成为朋友的时候，我们让a'与b'成为朋友，a与b'，b与a'成为敌人 当a和b成为敌人的时候，我们让a'与b'成为敌人，a与b'，b与a'成为朋友 如此我们就可以迅速判断多组输入时候的朋友与敌人关系了 例如1与2是敌人，2与3是敌人，3与4是敌人，4与5是敌人    问1与5什么关系    我们来建立模型        1与2是敌人& ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 先考虑一个简单的问题 $$f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$$ 我们这样来解决$$\begin{aligned}\&f(a,b,c,n)\&=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\&=f(a%c,b%c,c,n)+\sum_{i=0}^{n}(i\lfloor\frac{a}{c}\rfloor+\lfloor\frac{b}{c}\rfloor)\&=f(a%c,b%c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor\\&令m=\lfloor\frac ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial dp的意义代码中写的很清楚，唯一要注意的是，有一个卡常的地方，显然对于n个点m条边取k个点的斯坦纳树，我们的dp有意义开到dp[1<<k][n]吗？ 这里是不必的，我们只需要开到dp[1<<(k-1)][n]即可，很容易想到dp[(1<<k)-1][any]中对于所有0<any<=k都是答案,然而却不一定能想到 dp[(1<<(k-1))-1][k]也是答案，借此我们可以提升50%的时空性能 牛客上的题目 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687 ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 用最少条数的路径覆盖树，这是一个树dp问题 1234567891011121314151617181920212223void dfs(int u,int father){ int sum=0; for(int i=head[u];~i;i=edge[i].nex){ if(edge[i].v==father) continue; dfs(edge[i].v,u); sum+=dp[edge[i].v][0]; } dp[u][0]=sum+1;//子树路径覆盖的答案 dp[u][1]=sum+1; vector<int>update; for(int i=head[u];~i;i=edge[i].nex){ if(edge[i].v==fa ...