神奇思想——离线操作本文不讨论强制在线(允悲)

本文不讨论强制在线(允悲)

有一些看起来很不可做的题目,会有很多变态的条件和询问,让人摸不着头脑,但是这种题的题解中不乏一种神奇的小方法——离线处理。而且就我目前短浅的见识来看,这种做法多出现在数据结构和贪心中.

例题 P1972 [SDOI2009]HH的项链

题意

给定一个长度为(n)的数列(a),其中(a_i)是((1,1000000))之间的正整数.现在有(m)次询问,每次询问一个区间([l,r])中有多少种不同的值.

(1 le n,m le 1000000,1 le l,r le n)

解析

这个题乍一看像P1558 色板游戏,但是仔细一看,(a_i)的范围竟然是(1e6),显然不是一个题.

暴力

时间复杂度(O(nm)),数据加强之后堪称(TLE)自动机.

正解

对于同一个数,我们肯定只需要记录一次就可以了.但是我们记录那一次呢?最后一次.详细点说,我们设(next_i)表示数字(i)最后一次出现的位置.然后我们通过树状数组来统计次数.为什么要这样呢?因为区间不同数字种类数可以转化为每个数是否出现((1)或者(0)),然后用树状数组通过前缀和相减的方式来针对每一个询问统计区间内有多少不同的数.

回到做法,我们设置了(next)数组来记录数字出现的最后一次位置.这样对于一个询问,我们就找到从(1)到(r)每个数在区间([1,r])中最后出现的地方,将那里标记为1.然后(sum(r)-sum(l-1))即可.因为我们统计的是最后一次出现的位置,这就意味着(l)之前的"(1)"都不在([l,r])中,只有([l,r])中的"(1)"才属于这个区间.而且因为相同的数字我们没有多次统计,所以只要统计区间中"(1)"的个数就是不同的数的种类数.完美的转化为了前缀和问题.

上代码:

#include <cmath>
#include <queue>
#include <deque>
#include <cctype>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000005
using namespace std;

template<class T> inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch))
        w = (ch =='-'), ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

inline int lowbit(int x) {
    return -x & x;
}

struct node{
    int l, r, ind, ans;
}qsts[N];


int n, m, c[N], rtst[N], a[N];

inline void update(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
    return;
}

inline int sum(int x) {
    int ret = 0;
    while (x > 0) {
        ret += c[x];
        x -= lowbit(x);
    }
    return ret;
}

inline bool cmp(node x, node y) {
    return x.r < y.r;
}

inline bool cmp1(node x, node y) {
    return x.ind < y.ind;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    read(m);
    for (int i = 1; i <= m; ++i) {
        read(qsts[i].l), read(qsts[i].r);
        qsts[i].ind = i;
    }
    sort(qsts + 1, qsts + 1 + m, cmp);
    for (int i = 1, mark = 1; i <= m; ++i) {
        for (int j = mark; j <= qsts[i].r; j++) {
            if (rtst[a[j]])
                update(rtst[a[j]], -1);
            update(j, 1);
            rtst[a[j]] = j;
        }
        mark = qsts[i].r + 1;
        qsts[i].ans = sum(qsts[i].r) - sum(qsts[i].l - 1);
    }
    sort(qsts + 1, qsts + 1 + m, cmp1);
    for (int i = 1; i <= m; ++i) {
        printf("%dn", qsts[i].ans);
    }
    return 0;
}

例2 P1955 [NOI2015]程序自动分析

题意

给出n个形如(x_i=x_j)或者(x_i≠x_j)的关系,问是存在矛盾.

解析

这道题是一道很好的并查集练习题,因为我们知道相等关系具有美妙的传递性,而并查集也有美妙的传递性,于是我们可以在得到形如(x_i=x_j)的关系时,将(i)和(j)所在的并查集合并起来,然后如果得到了(x_i≠x_j)的关系的话,那显然是自相矛盾的.

但是存在一个操作次序的问题.如果先得到了(x_i≠x_j)呢?或者如果不止两个,而是多个(x)之间的关系乱序给出,又怎么判断呢?事情变得混乱起来.因此我们不能被它给出的次序牵着鼻子走.我们采用离线的方法,先读入所有关系,因为条件给出的顺序并不影响结果,所以我们先把等于的关系建立好了以后,再一一判断不等于的关系能不能符合.也就是说,把所有关系按照等于(>)不等于的关系先排序,按照所有等于关系建立并查集,然后对于每个不等于关系(x_i≠x_j),我们判断(i,j)在不在同一个并查集,如果不在,就继续,否则算法结束,输出矛盾.

顺便一说,因为值域很大,但是n很小,所以我们需要先离散化一下.

上代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int totq, n, father[1000005], lisanhua[3000000];

struct node {
    int from, to, e;
}sht[1000005];

inline bool cmp(node x, node y) {//关键
    return x.e > y.e;
}

int findfather(int x) {
    if (father[x] != x) 
        father[x] = findfather(father[x]);
    return father[x];
}

inline void chushihua(int what) {
    for (int i = 1; i <= what; i++) 
        father[i] = i;
}

int main() {
    cin >> totq;
    for (int P = 1; P <= totq; P++) {
        int tot = -1;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> sht[i].from >> sht[i].to >> sht[i].e,
        lisanhua[++tot] = sht[i].from, 
        lisanhua[++tot] = sht[i].to;
    sort(lisanhua, lisanhua + tot);
    int all = unique(lisanhua, lisanhua + tot) - lisanhua;
    for (int kk = 1; kk <= n; kk++) {
        sht[kk].from = lower_bound(lisanhua, lisanhua + all, sht[kk].from) - lisanhua;
        sht[kk].to = lower_bound(lisanhua, lisanhua + all, sht[kk].to) - lisanhua;
    }
    chushihua(all);
        sort(sht + 1, sht + 1 + n, cmp);
        int qwq = 1;
        while (sht[qwq].e == 1) {
            father[sht[qwq].from] = findfather(sht[qwq].from);
            father[sht[qwq].to] = findfather(sht[qwq].to);
            father[father[sht[qwq].to]] = father[sht[qwq].from];
            qwq++;
        }
        bool flag = 0;
        while (sht[qwq].e == 0) {
            if (qwq > n) break;
            if (findfather(sht[qwq].from) == findfather(sht[qwq].to)) {
                cout << "NO" << endl;
                flag = 1;
                break;
            }
            qwq++;
        }
        if (!flag) cout<<"YES"<<endl;
        memset(sht, 0, sizeof(sht));
    }
    return 0;
}