splay STL    发布于 2020-09-19   145人围观   0条评论

题目大意

维护一个多重集合,支持三种操作:

  • 1 : 加入一个x
  • 2 : 删除一个x
  • 3 : 询问当前在多重集中,是否存在两个数a,b,使得x能与a,b组成一个合法的三角形

题解

这题有线段树动态建点和离线离散化建线段树的做法,但是平衡树的做法一定是最好想的。

考虑查询操作我们可以假设下面两种情况:

  1. x为唯一最大边,则要a,b都小于x,于是只需要找比x更小的两个前驱作为a,b,判断a+b>x是否成立即可。
  2. x不是唯一最大边,假设b≥a,于是我们需要b≥x && b - a < x,而b-a最小的条件一定是b确定的情况下,a是b的一个非严格前驱,这样我们只需要找x的后缀最小值就行了。

第一种情况非常简单,直接用multiset维护、查询就行了,只需要注意一下边界问题。

第二种情况比较麻烦,没法用STL做,所以就用平衡树维护。平衡树维护的信息为子树内相邻两数差的最小值,排序的键值为当前数的大小,查询答案的时候,找到x的后缀节点,然后判断此节点与前一个节点的差mnval和其右子树中的相邻两数差的最小值mn中的最小值是否<x即可。

需要注意考虑边界问题。

最后提示的一点,s.lower_bound(x)和s.upper_bound(x)是比lower_bound(s.begin(),s.end(),x)和upper_bound(s.beign(),s.end(),x)要快不少的。我就被坑了……。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
multiset<int>s;
const int maxn = 2e5+5;
typedef pair<int,int> PI;
struct splay_node{
    int siz;
    PI val;
    int mn;
    splay_node *fa,*ch[2];
    void update(){
        mn = min(val.second,min(ch[0]->mn,ch[1]->mn));
    }
    void set_ch(int type,splay_node *child);
    int get_wh(){
        return (this == this->fa->ch[0]) ? 0 : 1;
查看更多
bitset    发布于 2020-09-16   329人围观   0条评论

题目大意

给出一个长为n的数列A,一个长为m的数列B

求问A中有多少个长度为m的子区间S,满足S中的元素全都不小于B中下标对应的元素

题解

说实话真的还是对bitset的应用不熟悉。

这题bitset只是最后用来优化的。

首先我们假定一个tmp数组,其中tmp[i][j]表示对Ai是否≥Bj。

如果一个长度为m的子区间要成为满足题目条件的S,那么和tmp[i]数组有什么关系?

一定是要求:对于区间内每一个i及其对应位置的j,tmp[i][j]都为1.这是显然的。

考虑如何优化这个问题。

首先,大小关系其实本质上来说只有m+1种,也就是对于tmp[i]的取值最多有m+1种,所以我们可以将B数组内的数全部排序,然后用m+1个bitset(假设为s)逐位去置1,然后九不需要算tmp数组了,我们需要取用tmp的时候,只需要找到最后一个小于等于A[i]的B[j](这里的B已经排序好了),然后取s[j]就可以了。而且bitset也会在我们接下来的做法中发挥很重要的作用。预处理这些bitset的复杂度是O(m2/W)的(W为bitset优化的效果)

之后考虑如何去搞这个题。

新设一个新的m位bitset,假设为curi,其中curi[j] = 1当且仅当对于所有的k∈[j,m],Ai+k-j >= Bk,这样只需要求有多少curi[1] = 1即可。

首先可以确定A数组的后m-1个数是肯定不可以作为区间点的,毕竟区间长度都不够,所以我们可以按照下面的公式来做:

curi = ((curi+1 >> 1) | Im) & sposi。posi表示最后一个小于等于A[i]的B[posi]。

这样通过右移位来进行对齐,可以达到我们预期的效果。

而且,我们可以不用开n个cur,只需要开一个进行滚动就可以了。

最终的时间复杂度是O(nm/W)

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PI;
const int maxn = 150005;
const int maxm = 40005;
PI a[maxn],b[maxm];
bitset<maxm>s[maxm];
bitset<maxm>cur,upd;
const int INF = 1e9+7;
int n,m;
int p;
int main(){
    ios_ba
查看更多
字符串 Trie 后缀自动机    发布于 2020-09-14   449人围观   0条评论

题目大意

对S串做两次f变换,得到一个字符串集A,求A中本质不同的字符串数量。

题解

其实不管是观察,还是拿样例手算,最后一定能得出一个结论:

其实两次f变换和一次f变换的作用是一样的。

所以只需要看一下一次f变换就行了。

f其实是对子串的变换,后面被变换的字符只跟其前面的字典序比他大的字符有关。

先看题目要求,求A中本质不同的字符串数量。

前面说了A实际上是S的所有子串做了变换而已。所以也就是本质不同的类子串数量(这个说法大概可以吧)。所以很自然想到这是一个后缀自动机。

但是这里的要求的并不是简单的子串,需要做变化。

前面说了,被变换的字符只跟其前面的字典序比他大的字典序最大的字符有关,只要出现一个比他大的字符就要重新更新字符串。

于是我们可以这样搞:

我们考虑将原串倒过来,然后按照题目的要求去建一个Trie,具体建法比较麻烦,如果当前字符的上一个比他大的字符没有出现,则需要从根开始往下重新建一条链,否则就继续往下建,复杂度最大为O(10n),但实际上肯定到不了。

然后对Trie静态建广义后缀自动机,直接跑本质不同子串数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],maxlen[maxn],trans[maxn][10];
    queue<int>q;
    ll ans;
    void init(){
        tot = 1;
        return;
    }
    int extend(int ch,int last){
        int x,y,z = ++tot;
        int p = last;
        maxlen[z] = maxlen[last]+1;
        while(p && !trans[p][ch])
            trans[p][ch] = z
查看更多
网络流 费用流    发布于 2020-09-12   483人围观   0条评论


题解

我记得当年我在考场上做这个题的时候想出了很多奇奇怪怪的思路……反正就是不会处理上下界的问题,然后就这个题爆零了

实际上我已经想明白是上下界的费用流了,但是并不会有上下界的情况,所以只能想各种奇技淫巧。

所以,此题的正解就是无源汇有上下界的最小费用可行流。

对于无源汇的网络流问题,我们通常会设置虚拟源点S和虚拟汇点T。然后再在图上进行构建。

对于这个题也是一样,只是因为有上下界所以我们需要对图进行一下改进。

我们考虑一条边一定会流下界那么多的流,这样整张图的残量网络就构成了一个流量不平衡的图。我们需要构建另外一张流量不平衡的图,使得原始图和我们构建的图互补成为一张流量平衡的图。

我们考虑对于原图中进行统计,一个点每流出1流量,度数du[x]-1,流入1流量,度数du[x]+1。

如果最终一个点的度数<0(流出大于流入),则其在互补图中流入就要大于流出,这样我们就需要给他添加一些流出渠道来疏通这些多余的流入流量,这样就从点x向虚拟汇点T连一条容量为-du[x]的边。反之同理。

如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的与原图互补的附加流。

那么怎样找出一个新加的边都满流的流呢?可以发现假如存在这样的方案,这样的流一定是我们所建出的图的S-T最大流,所以跑S到T的最大流即可.如果最大流的大小等于S出发的所有边的流量上限之和(此时指向T的边也一定满流,因为这两部分边的流量上限之和相等),则说明此图是有可行流的.

在此题中也是如此,只是原图上的边加上了费用而已,而新加的边费用为0,直接跑有上下界最大费用可行流即可。

代码

#include <bits/stdc++.h>
using namespace std;
int T,S,E;
const int maxn = 205;
const int INF = 2e9;
struct edge{
    int fr,to,next,cap,dis;
}e[maxn<<3];
int h[maxn];
int cnt = 0;
void add(int u,int v,int cap,int d){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = cap;e[cnt].dis = d;e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr
查看更多
线性基    发布于 2020-08-18   241人围观   0条评论

题目大意

玩家Little Sub和lqybzx分别有N、M个数对(xi,yi)、(x'i,y'i),且双方都知道对方的数对中的数是什么,Little Sub先从自己的N个数对中的每个数对中选取1个数z,并且ans = ans xor z,之后lqybzx会对自己的M个数对做相同的操作。

Little Sub(A)希望最终结果更大,而lqybzx(B)希望最终结果更小,且双方均采取最优策略,问最终答案是多少。

题解

对于博弈的题目来说,我们其实不是好知道双方的脑回路是怎么想的。有时候我们能猜到有时候我们猜不到。

所以不妨我们先来假设两个人每个数对都选第一个数字,先把一个答案ans算出来,然后我们来根据每个人的数对再来进行调整。

由于是二进制的运算所以我们考虑对每个答案ans的每个二进制位上是否为1来讨论两个玩家的策略。

因为我们需要对二进制位进行讨论,所以我们需要讨论两个玩家的数对(x,y)中x xor y对答案的控制能力。所以我们需要对两个玩家的数对(x,y)进行x xor y的线性基的构造。

假设构造的两个x xor y的线性基分别为A、B。

如果在某个位bit上我们取了线性基X中在bit位上的元素,我们相当于在总答案的上面对某一组数对(x,y)的选择进行改变(ans xor(x xor y),本来ans中有x或y,选择这一次相当于换成另外一个)

我们从高位到低位逐一进行扫描,对于第i位,分为以下八种情况:

ans[i] = 0,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 0,A[i] = 0,B[i] = 1,只有B对这个位可以操作,但由于B想要答案更小,所以他不会对这一位进行操作。

ans[i] = 0,A[i] = 1,B[i] = 0,只有A对这个位可以操作,由于A想要答案更大,所以他会选择对这一位进行操作,ans ^= A[i]。

ans[i] = 0,A[i] = 1,B[i] = 1,A与B都可对这个位操作,而且如果A对这个位操作的话,B一定也会对这个位操作,所以我们可以把A[i] xor B[i]加入到线性基A中,表示A和B同时选/不选。

ans[i] = 1,A[i] = 0,B[i] = 0,双方都对这个位无法操作

ans[i] = 1,A[i] = 0,B[i] = 1,只有B对这个位可以操作,由于B想要答案更小,所以他会选择对这一位进行

查看更多
DP 虚树    发布于 2020-07-12   196人围观   0条评论

 

题解

本人的虚树入门题。

基础思想

题目意思相当于m次询问,每次询问给出一些点,要我们付出一定代价断边使得给出的这些点与根节点1不连通.

首先肯定能确定这个题是一个树形DP。转移方程也非常好写。

考虑对于单次询问,我们设f[x]为处理完以x为子树的最小的代价。

那么转移无非是两种情况:

1.断开与父亲的连接,代价为从x到根1的路径上的最小值。

2.当该点不是询问点的时候,把子树内所有询问点都与根节点断开的代价。

但是这样有一个问题,每次询问都是O(n)的,来看一下数据范围:

很明显O(nm)的做法是无法处理的。

进阶优化 & 虚树的引出

但实际上,我们在对每一次询问的处理中,考虑了很多无用点的信息。

考虑一下,很容易能够明白,实际上,只有询问点、其LCA、其LCA的LCA及其三次LCA……等,对这些点和上面的根进行断开是实际在最小答案中有效的,处理其他的点实际上无效。

所以虚树就应运而生了。

虚树是主要运用在树形DP中的一类构造方法,旨在只将对答案有用的点拿出来构造一棵虚拟的新的树,以此来降低算法的复杂度。

举个栗子,在本题的样例中有这样的数据。

对于样例中的询问数据

3
2 10 6
4 5 7 8 3
3 9 4 6

其对应的虚树分别是以下的形式

第二个询问中,由于点7、8均在5的子树内,故断开5以及根节点的连接即可,7、8实际上是无用点(仅对此题而言,不同题目要考虑不同的构造)

虚树的构建

现在需要考虑的是如何构建虚树。

首先我们要先对整棵树dfs一遍,求出他们的dfs序,然后对每个节点以dfs序为关键字从小到大排序(本人比较喜欢用树链剖分里面的那种形式)

同时维护一个栈,表示从根到栈顶元素这条链

假设当前要加入的节点为pp,栈顶元素为x=s[top]x=s[top]lcalca为他们的最近公共祖先

因为我们是按照dfs序遍历,因此lcalca不可能是pp

那么现在会有两种情况

  1. lcalcaxx,直接将
查看更多
树链剖分    发布于 2020-04-16   473人围观   0条评论

题目大意

给出一棵n个节点的树,要求将这个树的所有节点映射到一张1000000*20的横向表格里,要求保持原先的连边映射成的相连线段不能有交叉。

输出一种方案,要求将所有的树上节点的坐标输出。

题解

行数最多只有20行,所以要考虑最大行数控制在log2n以内。所以就要想树上的什么东西一定小于小于等于log2n。

学过树链剖分的话不难想到,对一个树进行重链剖分的话,所有点向下的轻链长度一定小于等于log2n,树链剖分的复杂度就是基于这个性质证明的。这个性质的证明并不难想,因为对于一个节点x,其轻儿子的子树大小一定不会超过siz[x]/2,否则这个儿子就是重儿子了。

然后就可以明白,要先对树进行重链剖分,对每个节点now把重儿子和自己放在同一行上,轻儿子放在下一行,重儿子和自己的距离间隔为siz[now]-siz[son[now]],第一个轻儿子v1放在(x[now],y[now]+1),第二个轻儿子v2放在(x[now]+siz[v1],y[now]+1),第三个轻儿子v3放在(x[now]+siz[v1]+siz[v2],y+1),以此类推。

因为横向的列数极多,所以横向不会出现问题,又由轻链长度的性质,纵向不会不会超过20.上述的放节点的留空就是为了使得边不会交叉采取的方案。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+5;
vector<int>g[maxn];
int son[maxn],siz[maxn],f[maxn];
struct point{
    int x,y;
}p[maxn];
void dfs(int now,int fa){
    siz[now] = 1;
    son[now] = 0;
    f[now] = fa;
    for(auto it : g[now]){
        if(it == fa)continue;
        dfs(it,now);
        siz[now] += siz[it];
        if(siz[it] > siz[son[now]])
            son[now] = it;
    }
    return;
}
void work(int now,int 
查看更多
高斯消元 bitset    发布于 2020-04-16   559人围观   0条评论

题目大意

给出n个k维向量vi,对于k维空间中所有点a,将点a与点a+vi连边,求问全部连接完的图能否完成黑白染色。

题解

黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。

考虑二分图形成的条件:不能出现奇环。

于是问题就转变成了如何判断图中是否会存在奇环。

但是这个题目明显不能用通常的搜索判环解决。

考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。

假设n个未知数xi,假设一个点想要回到自身,需要使用第i个向量xi次。

于是要形成环即向量方程:

x1v1 + x2v2 + ... + xnvn = 0有解。

所以如果要保证形成奇数环的话,就是加入以下一个方程

xxor x2 xor ... xor xn = 1

联立来解一个n元k+1维方程组。

将上面的向量方程拆分到k维k个方程,并将所有运算全都mod 2处理,即可让整个方程组变成一个异或方程组。

能形成二分图的条件就是方程组不存在解,否则就说明构成的图不是二分图。

使用高斯消元解决方程组判断解的问题。

但是高斯消元有一个问题,就是复杂度不对,为O(nk2)

不过由于这道题的方程组的运算只与二进制异或有关,所以可以把方程的参数放入bitset加速,最终复杂度为O(nk2/64)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
bitset<maxn>g[maxn];
int n,k,now,x;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= k;++j){
            cin >> x;
            g[j][i] = abs(x) % 2;
        }
    }
    for(int i = 1;i <= n+1;++i){
        g[k+1][i] = 1;
    }
    now = 0;
    for(int i = 1;i <= n;++i){
        int j
查看更多
dsu on tree 树链剖分    发布于 2020-04-05   354人围观   0条评论

Example

15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3

题目大意

给出一棵有根树,树上每个点有一个颜色,求问以每一个节点x为根的子树内数量最多的颜色的编号的和sum为多少。

题解

如果暴力统计的话,时间复杂度将会成为O(n2),这是我们没办法接受的。

貌似可以搞什么线段树合并还有莫队什么的。

但是复杂度好像依旧还是太高,于是就有这么一个神奇的东西叫dsu on tree,中文名叫树上启发式合并。

dsu实际上是并查集的问题,但这个算法并不是什么树上并查集,而是借鉴了并查集中启发式合并优化的思想,将这个思想运用到了树上。

结合树链剖分的性质,将所有的树链分为轻链和重链后,对于每一个子树的根节点rt:轻链子节点sq,递归进入计算以sq为根的子树的答案,但是不保存,递归结束时清空;重链子节点son,递归进入计算以son为根的子树的答案,递归结束时不清空,作为rt为根节点的子树的基础答案。

之后对于以rt为根节点的子树,在重链子节点son的子树提供的基础答案上,再暴力计算该子树其它所有轻链子树和rt节点本身的答案,与刚刚的基础答案合并,可以解算出以rt为根节点的子树的答案。

通过树链剖分的轻重链性质,不难证明答案的复杂度应该为O(nlog2n),因为所有节点被访问的次数至多为log2n次。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int x,y;
typedef long long ll;
ll ans[maxn],c[maxn],sum,mx;
int son[maxn],siz[maxn],f[maxn],cnt[maxn];
vector<int>g[maxn];
int n,s;
void dfs(int now,int fa){
    f[now] = fa;
    siz[now] = 1;
    for(auto it : g[now]){
        if(it == fa)continue;
        dfs(it,now);
        siz[now
查看更多
数论 筛法 mobius反演 min25筛    发布于 2020-03-29   111人围观   0条评论

title

题目大意

给出一张n个点的完全图,两点ij (i<j)的路径的距离被定义为:
dis(i,j)=mink[ijk=x2,xZ+]
dij 表示i到j的最短距离,求1i<jndij

题解

题目挺绕的,可能会让人误以为是图论题。但是一看数据范围就不是。所以就来考虑最短路的性质。
显然的,假设节点i,j的编号分别被进行了质因子分解,表达成唯一分解定理的表达式,那么两点的最短距离,如果在两节点编号各质因子的幂次的奇偶性均相同时为1,否则一定为:
dij=pk[i=xpkn,j=ypkm] 其中x,y均没有pk为因子,且n,m奇偶性不同。
很简单,如果两点有多个因子不同,那么我们完全可以途经其它节点来走,让质因子相加取代相乘,这样一定是最小的。
于是就可以直接分最短路径为1和不为1两种情况来讨论。
首先讨论为1的情况,这种情况下我们把两数a,b指数为奇数的pk乘在一起,假设为c,这样ac,bc就是两个介于[1,nc]

查看更多