【线段树】区间不重复覆盖

传送门

题目意思是依次给n个区间，长度为1或者2，让从里面选一些区间，使得1到m都被覆盖。并且选出区间的编号差要最小。

用双指针求取最短编号差。

难点在于怎么动态确定区间是否被覆盖了。

对于一个点，可能被三种区间覆盖，于是我们对于区间的端点进行分类。用_表示可以被填的方块类型。

“_LR” 代表区间左端点可以填为长度为1或者2的右端点，但右端点不超出。即可能向左超出
“LR_” 代表区间右端点可以填为长度为1或者2的左端点，但左端点不超出。即可能向右超出
“_LR_” 代表左右端点都有可能超出。
“L_R” 代表左右端点都不超出。

然后用线段树维护这四个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
struct Node{
    int _lr, lr_, l_r, _lr_;
}tr[maxn << 2];
int c1[maxn], c2[maxn];
void maintain(int rt, int l, int r)
{
    if(l == r)
    {
        tr[rt].l_r = c1[l];
        tr[rt].lr_ = tr[rt]._lr = 1;
        tr[rt]._lr_ = 0;
    }
    else 
    {
        int mid = (l + r) >> 1;
        tr[rt].l_r = ((tr[rt << 1].l_r && tr[rt << 

股票问题集合

股票问题汇总

股票问题，指给定一系列数列，可以在某些天以当天价格买入，也可以在某些天以当天价格卖出。

按照买卖规则，可以分为：
1. 不能进行多笔交易；买股票之前只能先把手上的股票卖出。一般此类题是dp。
2. 可以进行多笔交易；手里可以同时持有多只股票。一般要贪心。

股票问题的核心是发现如何使得手里的资产最多。

无论是哪种模型，都可以看成如果第二天价格更高就卖，大不了可以反悔（可以以这天的价格再把卖掉的股票再买回来）。

问题1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int w[maxn], f[maxn][110][2];
int main()
{
    int n, k; scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    memset(f, 0xcf, sizeof f);
    for(int i = 0; i <= n; i++) f[i][0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            f[i][j][0] = max(f[i - 

【2017四川省赛/牛客】2017 Revenge【数论/指标】

传送门

题意是说给2e6个数，每个数都小于2017，从中选取一些数字使得乘积模2017等于给定的r，问方案数%2输出

DP，f[i][ja[i]%2017]=f[i-1][j]+f[i-1][ja[i]]，因为答案只需要奇偶，所以考虑异或操作。

不过这样的复杂度是2017n的。

考虑把乘法变成加法，5是2017的原根，并且2017是质数，剩余系是完全剩余系。所以把1-2016的指标存下来到I[]里面。

f[i][j+I[a[i]]]=f[i-1][j]+f[i-1][j+I[a[i]]]

可以把f开成一个bitset，f[i]表示第i个指标的方案数。所有的状态j每次加一个数I，就相当于循环左移了I位。再用异或滚动状态就可以了。

f^=(f<<I[a[i]])^(f(2016-a[i]))

#include<bits/stdc++.h>
using namespace std;
bitset<2016> f;
int a[2000002], I[2020];
int main()
{
    int n, r;
    int g = 1;
    for(int i = 1; i <= 2016; i++) 
    {
        g = g * 5 % 2017;
        I[g] = i;
    }
    // I[1] = 0;
    while(~scanf("%d%d", &n, &r))
    {
        f.reset();
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        f.set(0);
        for(int i = 1; i <= n; i++)
        {
            f 

【最短路/拆点】ACwing176

传送门

把每个点拆成100个点，分别表示到这个点的时候油量剩余的状态。跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int p[maxn], val[maxn], e[maxn], pre[maxn], h[maxn], cnt;
void add(int u, int v, int w)
{
    e[cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt++;
}
struct Ver{
    int a, b, c;
    bool operator<(const Ver &W)const 
    {
        return c > W.c;
    }
};
int dis[1010][110];
bool vis[1010][110];
int dijkstra(int cost, int start, int end)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis,0, sizeof vis);
    priority_queue<Ver> pq;
    pq.push({start, 

【min_25筛】筛欧拉函数、莫比乌斯函数、积性函数

传送门：欧拉函数、莫比乌斯函数

花了一下午学了一下min25筛。

一知半解。不过还是学会了套板子。

mu函数要看成质数个数取反，在预处理g的时候不能带负数（我也不知道为什么）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
ll primes[maxn], cnt;
bool st[maxn];
ll sp1[maxn], sp2[maxn], g1[maxn], g2[maxn], sm[maxn], g[maxn], w[maxn], wcnt;
ll id1[maxn], id2[maxn];
ll inv2, inv6, qn;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n;
        n = n * n ;
        k >>= 1;
    }
    return res;
}
void get_primes(int n)
{
    for(int i = 

【树状数组】query

传送门

题意是给一个长度为n的排列。给出m个询问，每次询问一个区间。

问区间内所有数一个数是另一个数的倍数的对数。

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

由于是排列，n<=1e5，所以用pos[i]存下i这个数的为位置。

在nlogn的时间里可以找出所有pair的对数，并以(l,r)的二元组表示。

再把询问L,R以二元组的形式离线。

问题转化成了二维偏序问题：L \le l \ \text{and}\ r \le R

用树状数组即可解决

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] ++ ;
}
int ask(int x)
{
    int res = 0;
    

【博弈】HDU 1079 Calendar Game

传送门

题意是说，给定一个日期，每个人可以轮流操作，要么将日期+1变为下一天，要么将日期变为下个月的同一天。

当下个月没有同一天的时候，只能讲日期变为下一天。

谁把日期变为2001.11.4即胜利。

是用sg函数做的。

当局面的sg=1的时候必胜。

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
bool check(int y, int m, int d)
{
    if(y > 2001) return 0;
    else if(y == 2001 && m > 11)  return 0;
    else if(y == 2001 && m==11 && d > 4) return 0;
    return 1;
}
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << 

【杜教筛】HUD-6706 huntian oy

传送门

题意：f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)
给定n,a,b求f

打表可知f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i (i-j)[gcd(i,j)=1]\%(10^9+7)

即：\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ i\ [gcd(i,j)=1]-\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ j\ [gcd(i,j)=1]

在i j互质的时候才有值。前面一部分就是每个数与其互质的个数的和，\sum\limits_{i=1}^{n}i\varphi(i)

后面一部分是每个数，与其互质的数值的和。\sum\limits_{i=1}^{n}\frac{i\varphi(i)}{2}(n1)

原因是gcd(n,x)=gcd(n,n-x)，当出现一个与n互质的数x的时候必然有一个n-x成对出现与其互质。他们的和为\frac{n}{2}，但这只是在n1的时候成立。

由于n==1的时候只有一个数字1，所以式子完整来写应该是\sum\limits_{i=1}^{n}\frac{i\varphi(i)+1}{2}因为在i=1的时候答案是1，如果除2就成了1/2，所以在分子上加个1使其成立

完整式子是\sum\limits_{i=1}^{n}\frac{i\varphi(i)-1}{2}

由于n有1e9，线筛是存不下的。
考虑
f=i\varphi(i)=id\varphi(i)
g=id
f*g(n)=\sum\limits_{i|n}\varphi(i)i\frac{n}{i}=n\sum\limits_{i|n}\varphi(i)

然后套杜教筛的板子。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv2, inv6;
bool st[maxn];
int primes[maxn], cnt;
ll phi[maxn];
unordered_map<int, ll> up;
ll ksm(ll n, ll k)
{
    

【权值线段树】HDU6703-array

传送门

题意是说给定一个排列，长度1e5，要求支持两种操作：
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。

经过分析，答案最大不可能超过n+1。这样的话，操作1其实相当于把这个数字从排列中删去。

用两棵权值线段树，每个点上存的是位置。

对每次2操作，在[k,n]区间里找最靠左的并且val[x]大于r的数。

对每次1操作，最开始是初始化一颗每个点值都是n+1的权值线段树，删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。

同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。

两个数取最小就是答案。

同时还需记录区间最大最小值，以用来在查询的时候剪枝。

没有这个剪枝，查询会退化为n^2log(n)的，因为区间里可能每个数都会递归到底。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;

struct Node{
    int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
    if(l == r)
    {
        t1[p].l = l, t1[p].r = 

【19HDU多校】Rikka with Coin，贪心

传送门

题意是说有面值10 20 50 100的钱，有n个价格给定的菜，要求用最少的硬币数量，使得所有n个菜品的价格都能被凑出来。

贪心：直观想法是先用大的面值，依次用小的面值。

这样的话可以发现10， 20， 20， 50四个面值能凑出所有100以内的价格。

但是有个例外：90 110 这样的数据，如果按照上面的贪法是100 50 20 20 10五个硬币，实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替，四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100和dish[i] % 100在某个组合的子集生成里有没有。（有先后顺序，第一个如果有了第二个就不用判断。因为既然零钱数量是固定的，那么100圆的越少约好）如果有，100圆的数量就分别是(dish[i] - （dish[i] % 100 + 100）/ 100) ，和dish[i] / 100。

对于100圆判断是个重要细节。
比如1000 90 110这样的数据，1000其中的100圆可以用零钱拼出来，所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20,