题目大意

一开始有一个初始顺序的排列[1,n]，一共有m次操作，每次将数ai从序列中取出，放到最开头的位置生成一个新的排列。

求问在所有过程中每一个数最小的下标位置和最大的下标位置。

题解

最小的下标位置是非常容易求得的，这很明显，因为如果从来没有被放到开头，那么答案一定是i，否则答案就是1。

需要思考的点在于求最大的下标位置。

这个数据范围不允许进行模拟，链表也不行（链表的单个操作、查询效率极差）。

先来考虑一种特殊情况1：

假设当前所有的数字都已经被放置到第一位过了，在满足这种条件后的最大的下标位置怎么求。

明显元素之间一开始的位置在哪里已经完全互不影响了。

如果一个数再被要求放到第一位，那么这个操作之前的下标位置可能就会影响答案。

而这个下标位置是什么？我们想什么样的操作会影响这个下标位置。很明显只有在上一次此数被放到第一位的时间之后，不同的数字放置到第一位才会使得这个数字的位置向后推移。也就是说，这个下标位置，就是当前未操作时刻和上一次这个数被放到第一位以后的时刻，这之间的不同数字的个数再+1，也就是区间内不同数的个数。

树状数组可以离线询问区间内不同数的个数。由于这道题的特殊性，我们无需对询问区间进行右端点优先排序，直接操作查询即可。

然后再考虑剩下的情况2：

如果一个数之前没有被放置在第一位的经历该如何计算？

这样在它被第一次放置到第一位的命令执行以前，其最大下标位置是之前的时刻被放置在第一位的大于此数的数字的个数 + 此数最初的坐标值。问题变成了维护区间内出现的不同数字的个数，需要用另外一个树状数组进行维护，只需要再每个数字第一次被放置在第一位时维护一次，查询一次即可。

在问题的最后，这样不一定已经求得最大值，因为对于每一个数字，最后可能有影响到最大值的问题但是没有查询更新。

所以在最后我们就要：

对于在操作序列中出现过的数字，我们执行情况1的查询一次。

对于未在操作序列中出现过的数字，我们执行情况2的查询一次。

代码

#include <bits/stdc++.h>
const int maxn = 3e5+5;
using namespace std;
map<int,int>mp;
int tr[maxn],a[maxn],ans[maxn],c[maxn];
int n,m;
int lowbit(int x){
	return x & (-x);
}
void add(int x,i

题目大意

给出n个模式串和一个匹配串，求问最少要修改匹配串中多少个字符才能使得匹配串中不含有任意一个模式串。

题解

多个模式串一定要用AC自动机的

所以首先把AC自动机给建出来

然后在AC自动机上跑DP，dp[i][j]表示当前匹配到长度为i，在AC自动机的Trie树上走到节点j的状态下的所需要修改的字符数量的最小值。

要注意不能走到模式串结尾的节点上。

在转移的时候，从当前状态向其子节点转移（前提是子节点非模式串结束的位置对应的节点），如果转移的节点的字符与字符串下一个字符相同，那么下一个状态的dp值继承当前状态dp值，代表不修改下一个字符的情况；否则下一个状态的dp值要在当前状态的dp值的基础上+1，表示修改下一个字符。

最后对dp[len][i]的所有值取min，即为最终答案。

（做这个题主要是为了写一遍AC自动机的板子）

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int INF = (1<<30)-1;
struct AC_auto{
    int next[4];
    bool flag;
    int fail;
}tr[maxn];
int root;
int index = 0;
int newnode(bool f){
    tr[index].flag = f;
    tr[index].fail = 0;
    for(int i = 0;i < 4;++i){
        tr[index].next[i] = 0;
    }
    return index++;
}
int n;
char ss[maxn];
int change(char c){
    switch(c){
        case 'A' : return 0;break;
        case 'T' : return 1;break;
        case 'G' : return 2;break;
        default : return 3;break;
    }
    return 0;
}
void build(char *s){
    int now = root;
    int len = strlen(s);
  

题目大意

给一个不完整的棋盘，每一列的方格数单调非升，问最多可以用多少个不重叠的1x2或者2x1的矩形覆盖棋盘（可以不完全覆盖）

题解

说实话思路比较巧妙

这种问题可以看成二分图匹配，相邻格子染色不同，假设分别染成黑白两种颜色，那么很明显想要用一个矩形覆盖，就必须要有一个黑格和一个白格匹配（两者相邻）。最大匹配数就是最终的答案。

但是这个数据范围过大，不能用匈牙利或者网络流解决。

注意到棋盘每一列的方格数是单调非升的，于是很明显只要先进行染色处理，然后从黑白格子中选出数量最少的那一种，其个数就是最大匹配数。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n;
long long ans;
long long a[maxn];
long long black,white;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        if(i & 1){
            black += a[i] / 2;
            white += (a[i] + 1) / 2;
        }
        else{
            black += (a[i] + 1) / 2;
            white += a[i] / 2;
        }
    }
    ans = min(black,white);
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF = 1e9;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn];
int p[maxn];
int d[maxn<<1],vis[maxn<<1];
deque<int>q;
int n;
struct edge{
    int to,next,cap,cost;
}e[maxn*maxn*2];
int S,T;
int h[maxn<<1];
int cnt = 0;
void add(int u,int v,int cap,int cost){
    e[cnt].to = v;e[cnt].cap = cap;e[cnt].cost = cost;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
bool spfa(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = -INF;
        vis[i] = 0;
    }
    d[t] = 0;
    vis[t] = 1;
    q.push_back(t);
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        vis[now] = 0;
        for(int i = h[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(e[i^1].cap && d[v] < d[now] - e[i].cost){
                d[v] = d[now] - e[i].cost;
                if(!vis[v]){
                    vis[v] = 1;
                    if(!q.empty() && d[q.front()] < d[v])q.push_front

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
const int INF = 0x3f3f3f3f
ll n, a[maxn],b[maxn],c[maxn],p[maxn];
ll w[maxn][maxn];
ll lx[maxn] , ly[maxn];
ll linker[maxn];
ll slack[maxn];
bool visy[maxn];
ll pre[maxn];
void bfs( ll k ){
    ll x , y = 0 , yy = 0 , delta;
    memset( pre , 0 , sizeof(pre) );
    for(int i = 1 ; i <= n ; i++ ) slack[i] = INF;
    linker[y] = k;
    while(1){
        x = linker[y]; delta = INF; visy[y] = true;
        for(int i = 1 ; i <= n ;i++ ){
            if( !visy[i] ){
                if( slack[i] > lx[x] + ly[i] - w[x][i] ){
                    slack[i] = lx[x] + ly[i] - w[x][i];
                    pre[i] = y;
                }
                if( slack[i] < delta ) delta = slack[i] , yy = i ;
            }
        }
        for(int i = 0 ; i <= n ; i++ ){
            if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
            else slack[i] -= delta;
        }
        y = yy ;
        if( linker[y

题目大意

给定一个序列，每次询问参数为pos和k，求问长度为pos的和最大的子序列中第k个元素是什么。

题解

这题其实有一个easy version，用map稍微搞一搞就能过那种

然后这题数据范围到2e5了，就不能用map乱搞了。

首先我们要想一下如何构造这个长为pos且和最大的子序列怎么构造呢？

我们只要对原序列从大到小排一次序，且保证在等大的时候原序列中靠前的元素在排序后也考前，然后我们只需要从排序后的序列中取前pos个数，就是符合要求的子序列了。

但是询问次数过多，我们就不能对于每一个request都重新求一次符合要求的子序列。

我们发现这个序列是递增的，就是如果pos[i] > pos[j]，那么询问i的序列一定就是询问j的序列再接上一段。

于是我们将询问也按照pos从小到大排序。

但是我们怎么找这个子序列中第k个元素是多少呢？

我们在对原序列进行排序的时候同时记录下元素在原序列中的位置，然后在选序列的时候，可以用这样一种经典的记录方式：

将当前被选中的元素加入树状数组进行计数，即将该元素对应的原序列的位置在树状数组上的位置进行update(pos,1)

当我们询问的时候，从1——n进行二分，统计在这个位置mid之前的选中数一共有多少个。

最终二分出来的答案就代表着选中序列第k位在原数组中的位置了。直接去原数组中找就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n,m;
int a[maxn];
int c[maxn];
int lowbit(int x){
    return x & -x;
}
void update(int pos,int x){
    while(pos <= n){
        c[pos] += x;
        pos += lowbit(pos);
    }
    return;
}
int val(int pos){
    int ret = 0;
    while(pos > 0){
        ret += c[pos];
        pos -= lowbit(pos);
    }
    return ret;
}
struct num{
    int id;
    int val;
}b[max

可持久化数据结构

众所周知，在竞赛界有这么一种神奇的解决方案，用以解决简单数据结构无法恢复历史版本的问题。

它就是可持久化！

如何可持久化？当然是要记录历史信息了。

但是那消耗空间不会巨大吗？

起始如果我们可以合理运用历史版本信息，我们就可以在创建新版本的时候尽可能地缩减需要的空间。

我们可以在当前版本复用未被修改地上一个版本的信息内存。

然而如何才能尽可能地去复用内存空间呢？这就需要树形结构了。

所以，对于所有的可持久化数据结构而言，都需要可持久化数组（一棵树）这样的基础。

怎么建立可持久化数组呢？可持久化数组的建立类似线段树，也就是可持久化线段树的建树过程。

所以说，可持久化线段树的建树是所有可持久化数据结构的学习基础。

可持久化并查集

并查集是一类用于判断图中两点是否连通的数据结构，其优点是时空复杂度低，但也有缺点，就是无法进行边的删除，只能进行边的添加。

如果我们要删除一些满足特定性质的边怎么办？比如删除最近添加的几条边？

显然最简单的并查集已经无法满足这个需求，所以我们借助可持久化数组将并查集升华成可持久化并查集。

并查集中有一个非常好的优化方法叫做路径压缩，但是如果在可持久化并查集中，这种优化方法就不适用了，因为它不能保持原来的各个连通块之间的关系，这样我们恢复历史版本的时候就会出问题。

为了使回溯历史版本时不出问题，再让并查集尽可能地优化，我们这里使用另外一种优化方法：按秩合并。

按秩合并的基本思路是：合并时将并查集树深度小的树根连到并查集树深度大的树根，以尽可能缩小并查集的深度。从而减少查找祖先的时间复杂度。

这种优化方法虽然没有路径压缩更优，但是非常契合可持久化的要求，所以拿来做可持久化并查集。

这里要注意，可持久化并查集中的可持久化数组的非叶子节点是没有意义的，只是拿来记录当前内存对应的原数组的下标区间，只有叶子节点才真正表示一个历史版本下某个节点的信息。

我们拆分成多个过程来看：

一、可持久化并查集的初始化建立

这一部分跟线段树差不多，只是到叶子节点的时候，其记录的信息要按照并查集按秩合并的初始化，将fa和dep全部初始化。

int build(int l,int r){
    int now = ++cnt;
    tr[now].l = l;
    tr[now].r = r;
    tr[now].lc = tr[now].rc = tr[now].fa = tr[now].

题解

第一问快速幂

第二问是扩展欧几里得算法求不定方程

第三问使用BSGS算法求离散模对数

三个函数直接看代码吧……纯板子题……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get_num(){
    ll num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
ll y,z,p;
map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b > 0){
        if(b & 1){
            ret = ret * a;
            ret %= mod;
        }
        b >>= 1;
        a = a * a;
        a %= mod;
    }
    return ret;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(b == 0){
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b,a%b,d,x,y);
    ll tp = x;
    x = y;
    y = tp - (a / b) * y;
    return;
}
void BSGS(ll y,ll z,ll p){
    mp.clear();
    y %= p;
    if(y == 0 && z == 0){
        cout << "1" 

题目大意

给出一些线段，给出这些线段的起始和终止位置，并给出这些线段选取的两个代价A和B，要求选取一些线段覆盖区间[1----t]，使得ΣAi与ΣBi的比值最小。

题解

很经典的01分数规划问题的形式。

当天训练的时候就想到了BUPT2019校赛的一道01分数规划问题，当时还是我们队拿的那题一血，可惜当时的队友现在因为一些原因分开了，真是令人感叹，sigh。

回归正题……

这一类最经典的01分数规划的解题基本思路是十分固定的，如下：

1.二分一个目标值mid

2.贪心地去构造检验是否有一组可行解，使得ΣAi / ΣBi <= mid;

3.如果能构造出这样一组可行解，那么将二分区间向左缩进，否则将二分区间向右缩进。

那么我们如何去构造这样一组可行解呢？

我们将不等式换一下形式，换成没有分式的不等式形式：mid * ΣBi - ΣAi >= 0；

这样我们就需要构造一组线段选取方案去满足上面的那个等式。

为了使得选取的区间完整，我们可以先将区间按照左端点为第一关键字，右端点为第二关键字从小到大进行排序，这样会保证在能构造出一组当前mid值条件下的可行解的时候我们不会漏掉中间的一部分区间。

之后我们先将所有mid * Bi - Ai >= 0的所有区间都选中，并统计加和sum，因为这些区间会使得不等式左边尽可能大。如果这时候已经能够覆盖所有需要覆盖的区间，那么就说明这样就已经能达到一组可行解了。

如果还没有覆盖所有区间，那么我们就要在剩下没有选中的线段中选取一些线段使得他们的ΣAi - mid * ΣBi尽可能小，这样不等式才能尽可能成立。

如何尽可能小？这时候我们可以使用树状数组去统计当前线段起点S前一个位置S-1到t的最小值（这里树状数组需要维护当前点到t的最小代价值），然后将选这个线段的方案统计入树状数组去求最小值。

之后我们去查询到t的最小值，判断sum是否大于等于 query(t)。如果sum >= query(t)，则满足上述不等式，二分区间向左缩进。否则将二分区间向右缩进。

为了保证二分精度，我们可以限定二分次数，而非用eps判定二分区间端点l与r的关系。具体实现见代码吧。

代码

#include <bits/stdc++.h>
using namespace std;
int n,t;
int T;
const int maxn = 1e5+5;
struct interv{
    int