首页 > 其他 > 详细

洛谷P4135 作诗

时间:2019-05-16 23:46:47      阅读:197      评论:0      收藏:0      [点我收藏+]

题意:N个数,M组询问,每次问[l,r]中有多少个数出现正偶数次。(强制在线)

强制在线,不能用莫队、树状数组等优雅算法,考虑暴力分块。

设分块后,f[i] [j] 表示第i块到第j块的答案。

于是,对于每次询问,设p为l所在块的编号,q为r所在块的编号,先查询l到r之间整块的答案,即f[p] [q]。

之后对于两边的不完整的块,暴力扫每个数,记录出现次数,与这个数在第p块和第q块之间出现的次数比较

  • 若这个数在两边的不完整的块和中间的整块中出现次数均为奇数,++ans
  • 若这个数在两边的不完整的块出现偶数次,在中间的整块中出现次数为0,++ans
  • 若这个数在两边的不完整的块出现奇数次,在中间的整块中出现次数为偶数且不为0,--ans

于是,问题关键在于如何快速求出某个数在任意两块间的出现次数。

记分块的数量为T,每块的长度len = n / T。序列长度n、询问次数m同阶。

解法一:

与 洛谷P4168 [Violet]蒲公英 类似,对每种数开一个vector,存下这个数在原序列中出现的位置,查询某个数在[L,R]出现次数,只需二分查找<=R的最大下标和>=L的最小下标作差+1.

如 1 2 2 1 2 3 2 这组数,查询2在[3,6]之间出现的次数。vector[2]={2,3,5,7},即2在原序列中出现的位置。二分查找<=6的最大数为5,在vector中下标为2(vector下标从0开始),之后再二分查找>=3的最小数为3,在vector中的下标为1,两个下标作差+1 = 2,即查询结果为2。

预处理时,从每个块的起点到n进行统计,复杂度\(O(T*n)\)

查询时,对两边不完整块的每个数需要二分查找,每次查找为\(logn\) ,共\(n/T\) 个数。

总时间复杂度\(O(nT+m(n/T*logn))\) ,空间为\(T^2\) ,取\(T=\sqrt{n*logn}\) ,此时总复杂度\(O(n\sqrt{n*logn})\)

注意:

  • 这里T如果取\(\sqrt n\) 会导致效率低下,\(\sqrt{n*logn}\) 约为\(\sqrt n\) 的三到四倍。
  • vector常数很大,再加上二分用STL中的lower_bound和upper_bound,常数上天。如果分块数量正确,开了O2之后勉强能过。
  • 可以手写二分,用数组代替vector,不开O2就能过。如果再加上一些卡常技巧(快读、inline、register等)跑的很快。

Code

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5, T = 1280;
vector<int> pos[N];
int n, c, m, len, tim, Stack[N], v[N], cnt[N], vis[N], block[N], bl[T], br[T], f[T][T];
inline void read(int &tmp) {
    register char c = getchar();
    for(tmp = 0; !isdigit(c); c = getchar());
    for(; isdigit(c); tmp = tmp * 10 + c - 48, c = getchar());
}
void init() {
    read(n);
    read(c);
    read(m);
    len = ceil(n * 1.0 / (sqrt(n * log(n))));
    for(int i = 1; i <= n; ++i) {
    read(v[i]);
        pos[v[i]].push_back(i);
        block[i] = (i - 1) / len + 1;
    }
    for(int i = 1; i <= block[n]; ++i) {
    bl[i] = (i - 1) * len + 1;
        br[i] = i * len;
    }
    br[block[n]] = n;
    for (int i = 1, res; i <= block[n]; ++i) {
    res = 0;
    for(int j = bl[i]; j <= n; ++j) cnt[v[j]] = 0;
        for (int j = bl[i]; j <= n; ++j) {
            ++cnt[v[j]];
            if ((cnt[v[j]] & 1) && (cnt[v[j]] > 1)) --res;
            else if (!(cnt[v[j]] & 1)) ++res;
            f[i][block[j]] = res;
        }
    }
}
inline int get(int x, int L, int R) {
    return upper_bound(pos[x].begin(), pos[x].end(), R) - lower_bound(pos[x].begin(), pos[x].end(), L);
}
int query(int L, int R) {
    int p = block[L], q = block[R], tp = 0, res = 0;
    if(q - p < 2) {//同块或相邻块
        for(int i = L; i <= R; ++i) {//暴力扫
            if(vis[v[i]] != tim) {//第一次扫到的标记
                vis[v[i]] = tim;
                cnt[v[i]] = 1;
            } else {
                ++cnt[v[i]];
                if(cnt[v[i]] & 1) --res;
                else ++res;
            }
        }
        return res;
    }
    res = f[p + 1][q - 1];//两块间的答案
    for(int i = L; i <= br[p]; ++i) {//左边角块
        if(vis[v[i]] != tim) {
            vis[v[i]] = tim;
            cnt[v[i]] = 1;
            Stack[++tp] = v[i];
        } else ++cnt[v[i]];
    }
    for(int i = bl[q]; i <= R; ++i) {//右边角块
        if(vis[v[i]] != tim) {
            vis[v[i]] = tim;
            cnt[v[i]] = 1;
            Stack[++tp] = v[i];
        } else ++cnt[v[i]];
    }
    while(tp) {
        int t = Stack[tp--], k = get(t, bl[p + 1], br[q - 1]);
        if(!k) {
            if(!(cnt[t] & 1)) ++res;
        } else if((k & 1) && (cnt[t] & 1)) ++res;
        else if(!(k & 1) && (cnt[t] & 1)) --res;
    }
    return res;
}
int main() {
    init();
    int res = 0;
    for(int i = 1, l, r; i <= m; ++i) {
        ++tim;
        read(l);
        read(r);
        l = (l + res) % n + 1;
        r = (r + res) % n + 1;
        if(l > r) swap(l, r);
        printf("%d\n", res = query(l, r));
    }
    return 0;
}

解法二:

利用前缀和思想,设g[i] [j]表示从序列开始到第i块中,数字j的出现次数。则查询数字x在第p+1块到第q-1块的出现次数,为g[q-1] [x] - g[p] [x]。

实际写的时候,可以把g数组定义为第i块到序列末尾中数字j的出现次数,即后缀和,方便在同一个循环中处理。查询时类似于前缀和。

这样每次查询为O(1),显然,总复杂度为\(O(n\sqrt n)\) ,空间为\((Tn)\)

理论复杂度比解法一快,实际上,当T取\(\sqrt n\) 时,不开O2有两个点会TLE(可能是我写的太丑了QAQ)。然鹅,T取较大值时,耗时更短,但空间会炸(要开T*n的二维数组...)

Code

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
using namespace std;
const int N = 1e5 + 5, T = 350;
int n, c, m, len, Stack[N], v[N], cnt[N], block[N], bl[T], br[T], f[T][T], g[T][N];
inline void read(int &tmp) {
    register char c = getchar();
    for(tmp = 0; !isdigit(c); c = getchar());
    for(; isdigit(c); tmp = tmp * 10 + c - 48, c = getchar());
}
void init() {
    read(n);
    read(c);
    read(m);
    len = sqrt(n);
    for(register int i = 1; i <= n; ++i) {
        read(v[i]);
        block[i] = (i - 1) / len + 1;
    }
    for(int i = 1; i <= block[n]; ++i) {
        bl[i] = (i - 1) * len + 1;
        br[i] = i * len;
    }
    br[block[n]] = n;
    for (int i = 1, res; i <= block[n]; ++i) {
        res = 0;
        for (int j = bl[i]; j <= n; ++j) {
            ++g[i][v[j]];
            if ((g[i][v[j]] & 1) && (g[i][v[j]] > 1)) --res;
            else if (!(g[i][v[j]] & 1)) ++res;
            f[i][block[j]] = res;
        }
    }
}
int query(int L, int R) {
    int p = block[L], q = block[R];
    register int res = 0, tp = 0, c, num;
    if(q - p < 2) {
        for(int i = L; i <= R; ++i) ++cnt[Stack[++tp] = v[i]];
        while(tp) {
            c = Stack[tp];
            if(cnt[c]) res += (cnt[c] & 1) ^ 1;
            cnt[Stack[tp--]] = 0;
        }
        return res;
    }
    res = f[p + 1][q - 1];
    for(int i = L; i <= br[p]; ++i) ++cnt[Stack[++tp] = v[i]];
    for(int i = bl[q]; i <= R; ++i) ++cnt[Stack[++tp] = v[i]];
    while(tp) {
        c = Stack[tp];
        if(cnt[c]) {
            num = g[p + 1][c] - g[q][c];
            if((num & 1) && (cnt[c] & 1)) ++res;
            else if(!(num & 1) && num && (cnt[c] & 1)) --res;
            else if(!num && !(cnt[c] & 1)) ++res;
        }
        cnt[Stack[tp--]] = 0;
    }
    return res;
}
int main() {
    init();
    int res = 0;
    for(register int i = 1, l, r; i <= m; ++i) {
        read(l);
        read(r);
        l = (l + res) % n + 1;
        r = (r + res) % n + 1;
        if(l > r) swap(l, r);
        printf("%d\n", res = query(l, r));
    }
    return 0;
}

洛谷P4135 作诗

原文:https://www.cnblogs.com/yu-xing/p/10878789.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!