首页 > 代码库 > CodeForces 455D 分块
CodeForces 455D 分块
题目链接：http://codeforces.com/problemset/problem/455/D
题意：给定一个长度为n的序列a[]。 m次操作。共有两种操作 1 l r:将序列的a[l].a[l+1]...a[r]变成a[r].a[l].a[l+1]...a[r-1]；2 l r k:求序列a[l].a[l+1]...a[r]中有多少个值为k。 输入的l,r,k都是加密过的。所以要解密一下。规则为 l=(l+ans-1)%n+1 r=(r+ans-1)%n+1 k=(k+ans-1)%n+1. （当解密过后l>r时交换l,r）ans为上一个2操作的结果。初始的ans为0. 即题目要求强制在线。
思路：考虑分块。每块维护一个cnt数组，cnt[i]表示在该块中数字i出现的次数。 再维护一个双端队列deque. 然后对于1操作就暴力来修改就好了。注意如果1操作涉及到多块的时候，要将第i块的最后一个移动到第i+1块的第一个。 然后维护一下cnt即可。
#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h> #include<string.h> #include<cstring>#include<algorithm> #include<queue> #include<math.h> #include<time.h>#include<vector>#include<iostream>#include<map>using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, q, val[MAXN];struct Node{ deque<int>Q; int cnt[MAXN];}Bval[400];void build(){ block = (int)sqrt(n + 0.5); num = n / block; if (n%block){ num++; } for (int i = 1; i <= num; i++){ memset(Bval[i].cnt, 0, sizeof(Bval[i].cnt)); Bval[i].Q.clear(); L[i] = (i - 1)*block + 1; R[i] = i*block; } R[num] = n; for (int i = 1; i <= n; i++){ belong[i] = ((i - 1) / block) + 1; } for (int i = 1; i <= num; i++){ for (int k = L[i]; k <= R[i]; k++){ Bval[i].cnt[val[k]]++; Bval[i].Q.push_back(val[k]); } }}void modify(int st, int ed){ deque<int>::iterator it; int v; if (belong[st] == belong[ed]){ it = Bval[belong[st]].Q.begin(); for (int i = L[belong[st]]; i < ed; i++){ it++; } v = *it; Bval[belong[st]].Q.erase(it); it = Bval[belong[st]].Q.begin(); for (int i = L[belong[st]]; i<st; i++){ it++; } Bval[belong[st]].Q.insert(it, v); return; } it = Bval[belong[ed]].Q.begin(); for (int i = L[belong[ed]]; i < ed; i++){ it++; } v = *it; Bval[belong[ed]].Q.erase(it); Bval[belong[ed]].cnt[v]--; it = Bval[belong[st]].Q.begin(); for (int i = L[belong[st]]; i < st; i++){ it++; } Bval[belong[st]].Q.insert(it, v); Bval[belong[st]].cnt[v]++; for (int i = belong[st] + 1; i <= belong[ed]; i++){ it = Bval[i - 1].Q.end() - 1; v = *it; Bval[i].Q.push_front(v); Bval[i].cnt[v]++; Bval[i - 1].cnt[v]--; Bval[i - 1].Q.erase(it); }}int query(int st, int ed, int v){ int ans = 0; deque<int>::iterator it; if (belong[st] == belong[ed]){ it = Bval[belong[st]].Q.begin(); for (int i = L[belong[st]]; i<st; i++){ it++; } for (int i = st; i <= ed; i++, it++){ ans += ((*it) == v); } return ans; } it = Bval[belong[st]].Q.begin(); for (int i = L[belong[st]]; i<st; i++){ it++; } for (int i = st; i <= R[belong[st]]; i++, it++){ ans += ((*it) == v); } for (int i = belong[st] + 1; i < belong[ed]; i++){ ans += Bval[i].cnt[v]; } it = Bval[belong[ed]].Q.begin(); for (int i = L[belong[ed]]; i <= ed; i++, it++){ ans += ((*it) == v); } return ans;}int main(){ //#ifdef kirito // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); //#endif // int start = clock(); while (~scanf("%d", &n)){ for (int i = 1; i <= n; i++){ scanf("%d", &val[i]); } build(); scanf("%d", &q); int type, l, r, v, ans = 0; for (int i = 1; i <= q; i++){ scanf("%d", &type); if (type == 1){ scanf("%d%d", &l, &r); l = ((l + ans - 1) % n) + 1; r = ((r + ans - 1) % n) + 1; if (l>r){ swap(l, r); } modify(l, r); } else{ scanf("%d%d%d", &l, &r, &v); l = ((l + ans - 1) % n) + 1; r = ((r + ans - 1) % n) + 1; v = ((v + ans - 1) % n + 1); if (l>r){ swap(l, r); } printf("%d\n", ans = query(l, r, v)); } } } //#ifdef LOCAL_TIME // cout << "[Finished in " << clock() - start << " ms]" << endl; //#endif return 0;}
CodeForces 455D 分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。