发表于 | 分类于 | | + s

BZOJ 3289
题意：不强制在线求区间逆序对。
离线莫队，右端点对逆序对答案的贡献等于当前区间所有大于右端点值的数的个数，可以用树状数组维护这个数。左端点类似，是所有小于左端点值的数的个数。

阅读全文 »

发表于 | 分类于 | | + s

caioj 1447
题意：给$n(1 \leq n \leq 50000)$个数字，进行$m(1 \leq m \leq 10000)$次操作，有两种操作：

$Q,l,r,k$：询问$l$到$r$第$k$小的数。
$C,x,k$：改变第$x$个数的值为$k$。

因为普通的主席树是前缀和套线段树，所以不能修改。那么我们想到修改，就发现可以用树状数组/线段树套线段树，由于此题单点修改，所以用树状数组。
对于前缀和套线段树先建主席树，然后再建树状数组套线段树的，修改在树状数组上操作，原数组在前缀和中，综合可以得到修改后的信息，要注意树状数组上的点在线段树上跳动(jump函数调节，存在$ust$数组)，查询就用$ust$数组即可

实际上可以不必要建$2n$棵线段树，原数组直接加到树状数组中即可，不过会慢一点，代码在下面

阅读全文 »

发表于 | 分类于 | | + s

caioj 1447
题意：维护区间和，有区间增加，要求可持久化 (回退、查询某个版本)

每个询问开一棵线段树，回退直接删掉中间的线段树即可。由于是主席树不能pushdown，pushup，所以增加的时候直接更新sumv的值，查询时lazy值直接累加乘以查询区间长度即可，具体操作可以看代码

阅读全文 »

发表于 | 分类于 | | + s

spoj DQUERY
caioj 1445
题意：给出一个$n$个数的序列，求区间$[l,r]$里有多少种不同数字。

树状数组离线作法：
我们将所有询问离线，按$r$排序。树状数组维护区间。然后不断根据询问向右加点加到$r$(排序避免删点)，如果当前数之前没有出现过，直接在树状数组该位置加$1$。否则就把之前出现这个值的位置减$1$，为的是把数尽可能放到右边，因为记录值中位置不影响答案。这样就方便求解$[l,r]$的信息，直接减即可，正确性显然，因为数都尽可能在右边。

主席树做法：
与树状数组类似，主席树维护区间，相当于可持久化维护每次加点后的情况。每个点按顺序建树，如果这个点的数之前没有出现过，直接在本棵主席树该位置加$1$。否则就把之前出现这个值的位置减$1$，再重复做没有出现的情况。为的是把数尽可能放到右边，因为记录值中位置不影响答案。这样就方便求解$[l,r]$的信息。
询问直接用右端点的主席树，由于上述操作后答案可减，所以直接把右端点的主席树左端点以右的值求和即可

阅读全文 »

发表于 | 分类于 | | + s

BZOJ 2724
题意：强制在线不修改求区间众数。
如果不强制在线，可以离线莫队直接处理。
这里强制在线，我们将原数列分块，预处理$i$块到$j$块区间的众数，直接开桶统计，用于求解整块的区间。
用vector把相同的数的位置按顺序存储下来，求众数可以用询问区间的每个数字去求他出现次数，比较即可。
对于整块，我们预处理了$i$块到$j$块区间的众数，直接询问这个数字在询问区间出现次数即可；
对于不完整的块，我们暴力每个数字在询问区间出现次数即可
最后输出即可，时间复杂度$O(m \cdot logn+\frac nm)$, 其中$n$为数列长，$m$为每个块长，根据均值不等式，在$m \cdot logn=\frac nm$时和有最小值，$m=\sqrt{\frac{n}{logn}}$，即得到最优分块大小

阅读全文 »

发表于 | 分类于 | | + s

模板及讲解

什么是主席树

主席树也称为函数式线段树、可持久化线段树，主要是利用动态开点每个点建线段树(维护$[1,i]$的区间)、线段树可加可减性($[x,y]=[1,y]-[1,x-1]$)来解决如区间内的某些问题。主席树实际上是树套树，最普通的主席树问题就是前缀和套线段树。

主席树的实现

例题

caioj 1441

给$n$（$1 \leq n \leq 100000$）个数字,
$a[1],a[2],……,a[n]（0 \leq a[i]<=1000000000）,m（1 \leq m \leq 100000）$次询问$l$到$r$之间的第$k$小的值。

由题不需要修改操作，就是最普通的主席树问题。

从全局入手

对于整个区间的$k$小，我们可以开权值线段树记录每个值的大小，然后查询时仿造平衡树的方法可以找到第$k$大值。

线段树可加可减性

那么对于区间$[x,y]$，我们怎么办？
想到每个点$i$开$[1,i]$的线段树(整个线段树维护区间不变，只是每个数值的范围，不然不能满足加减性), 则$[x,y]=[1,y]-[1,x-1]$

这样可以看出我们要研究线段树是否可加可减，看下面的例子(借用了 caioj 的图片)

两棵线段树显然可加，并且对应位置上的和相加(维护区间和)。

主席树实现

首先要对每个点开$[1,i]$的线段树，先开一条只包含$i$点信息的链，再与前面一棵线段树合并(相加)。合并线段树也很方便，只要加上$i$点的信息，合并$[1,i-1]$( $merge$ 操作，代码中的$mge$)

查询的时候类似平衡树的查询，例如求$k$小，因为权值线段树，所以左边点都小于这个点，右边点都大于这个点，判断一下第$k$小在左边还是右边，就可以找到了。

阅读全文 »

发表于 | 分类于 | | + s

第1题 Luogu P2734 游戏 A Game

Luogu P2734 游戏 A Game
题意：有一个序列，有两个玩家，每个玩家用最优策略在两端拿数，求先手拿到数字和的最大值。
解：由于两个玩家都采取最优策略，我们设$dp(i,j)$为区间$[i,j]$先手能得到的最优解。然后方程为$dp(i,j)=max(sum(i,j) - dp(i + 1, j), sum(i,j)-dp(i,j-1))$。$sum$是这一段的和。原理是区间DP的原理，整个区间$[i,j]$的先手，在$(i,j],[i,j)$是后手，$dp(i + 1, j), dp(i,j-1)$是$(i,j],[i,j)$的先手最优值

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, a[105], dp[105][105], sum[105][105];
void clean() {
    ms(dp, 0);
}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i][i] = a[i];
    for (int i = 1; i <= n; i++) {
        sum[i][i] = a[i];
        for (int j = i + 1; j <= n; j++) sum[i][j] = sum[i][j - 1] + a[j];
    }
    for (int i = n; i; i--) {
        for (int j = i + 1; j <= n; j++) {
            dp[i][j] = max(sum[i][j] - dp[i + 1][j], sum[i][j] - dp[i][j - 1]);
        }
    }
    printf("%d %d\n", dp[1][n], sum[1][n] - dp[1][n]);
    return 0;
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}
阅读全文 »

发表于 | 分类于 | | + s

第1题 NOIP2010 引水入城 (DFS+贪心)

NOIP2010 引水入城
题意：见上。
解：对第一行每个点 DFS 求出这个点可以覆盖最后一行的区间，然后对这些区间做最小完全区间覆盖$O(n^2)$即可。剪枝：如果第一行左右有比他高的，这个点不用继续搜索。Hack 点：如果n=1直接特判。
知识点：本题提供了一个思路，不需要枚举第一行设置的状态(1位置放、2位置不放……)，而是单独枚举每一种情况然后再进行操作。对于这种$n=500$规模的题目好用。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 500 + 10, INF = 1000000000;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, ans, ll[MAXN], rr[MAXN], h[MAXN][MAXN], vis[MAXN][MAXN];

void dfs(int x, int y, int k) {
    if (x == n) ll[k] = std::min(ll[k], y), rr[k] = std::max(rr[k], y);
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx > 0 && ty > 0 && tx <= n && ty <= m && vis[tx][ty] != k && h[tx][ty] < h[x][y]) vis[tx][ty] = k, dfs(tx, ty, k);
    }
}

void clean() {
    ms(vis, 0);
}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) scanf("%d", &h[i][j]);

    int gg = 0;
    for (int i = 1; i <= m; i++) if (!(h[1][i - 1] > h[1][i] || h[1][i + 1] > h[1][i])) ll[i] = INF, rr[i] = -INF, dfs(1, i, i), gg++;
    if (n == 1) return printf("1\n%d\n", gg), 0;

    //for (int i = 1; i <= m; i++) printf("i=%d l=%d r=%d\n", i, ll[i], rr[i]);
    int ans = 0;
    for (int i = 1; i <= m; i++) if (vis[n][i]) ans++;
    if (ans != m) return printf("0\n%d\n", m - ans), 0;

    ans = 0;
    int e = 0;
    while (e < m) {
        int mks = 0;
        for (int i = 1; i <= m; i++) if (ll[i] <= e + 1 && rr[i] > mks && rr[i] > e) mks = rr[i];
        ans++, e = mks;
    }
    printf("1\n%d\n", ans);

    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}
阅读全文 »

发表于 | 分类于 | | + s

第1题 CF 867E

CF 867E
题意：考虑股票市场，一共有$n$天。对于第$i$天，B君知道股票的价格是每单位$a_i$元
在每一天，可以选择买入一个单位的股票，卖出一个单位的股票，或者什么都不做。
刚开始有无穷多的钱，但是没有任何股票。
问$n$天之后最多可以赚多少钱。

解：用大根堆维护。从左往右扫，每次扫到一个数如果不大于当前堆的根，那么直接插。否则就先买(根和当前值)，然后再插两个当前值到堆里。相当于这次卖是一个中转点，不一定最终在这里卖。所以在后面如果有更优解那么将会继承中转点的值，也就是返回思想。

知识点：贪心思想可以用返回、中转点思想。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, t;
    LL ans = 0;
    priority_queue<int, vector<int >, greater<int > > q;

    void clean() {
    }
    int solve() {
        scanf("%d", &n);
        for (int x, i = 1; i <= n; ++i) {
            scanf("%d", &x);
            if (!q.empty() && x > q.top()) {
                ans += (LL)x - (LL)q.top();
                q.pop(); q.push(x);
            }
            q.push(x);
        }
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

第2题 Bzoj 4198

Bzoj 4198
题意：多叉哈夫曼树。
解：按照二叉树方法贪心是错的，最后在根节点会出现节点不够用的情况。所以我们可以修改一下，将下面的节点移到上面。具体是加一堆0点以至于$(n-1) \mod (k-1)=0$(画图分析)。对于第二问，贪心最小合并次数的合并即可，

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    struct data {
        LL val, tms;
        bool operator < (const data &rhs) const {
            if (val == rhs.val) return tms > rhs.tms;
            return val > rhs.val;
        }
    };

    LL n, k, ans, maxd;
    priority_queue<data > q;

    void clean() {
        maxd = ans = 0;
    }
    int solve() {
        clean();
        scanf("%lld%lld", &n, &k);
        for (LL x, i = 1; i <= n; ++i) scanf("%lld", &x), q.push((data){x, 0});
        while ((n - 1) % (k - 1) != 0) q.push((data){0, 0}), ++n;
        for (LL i = 1; i <= (n - 1) / (k - 1); ++i) {
            LL tmp1 = 0, tmp2 = 0;
            for (LL j = 1; j <= k; ++j) {
                data p = q.top(); q.pop();
                tmp1 += p.val, tmp2 = max(tmp2, p.tms);
            }
            maxd = max(maxd, tmp2 + 1);
            ans += tmp1;
            q.push((data){tmp1, tmp2 + 1});
        }
        printf("%lld\n%lld\n", ans, maxd);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}