codeforces 455D 分块

xiaoxiao2021-02-27  162

简略题意:初始给出长度为 n 的数组a[i], 有两种操作,共q次。 1.a[l],a[l+1],...,a[r]a[r]a[l]. 2.[l,r]k. 要求强制在线。

看起来就是个数据结构,然而我们很难找到一个成熟的模型来套。 那么考虑分块,对于操作1, 若 [l,r] 在同一块,直接暴力处理, O(n) ,否则我们只需要维护 n 个双端队列,对于 l 所在的块,r所在的块暴力处理,中间每一块 O(1) 处理,复杂度 O(n) . 对于操作2同理, O(n)

总复杂度 O(qn)

写起来还是需要注意细节的。

#include <bits/stdc++.h> #define all(x) x.begin(), x.end() using namespace std; typedef long long LL; const int maxn = 100002; int block, num, belong[maxn]; int mp[400][100001]; pair<int, int> mark[maxn]; deque<int> V[400]; int n; void build() { block = sqrt(n); num = n / block; if(n % block) num++; for(int i = 1; i <= n; i++) belong[i] = (i-1)/block+1; } void update(int l, int r) { pair<int, int> pos1 = mark[l], pos2 = mark[r]; int f1 = pos1.first, s1 = pos1.second; int f2 = pos2.first, s2 = pos2.second; int valr = V[f2][s2]; deque<int> &dq = V[f1]; if(f1 == f2) { dq.insert(dq.begin() + s1, valr); dq.erase(dq.begin() + s2 + 1); return ; } mp[f1][valr]++; V[f1].insert(dq.begin() + s1, valr); int vv = *V[f1].rbegin(); V[f1].pop_back(); mp[f1][vv]--; for(int i = f1 + 1; i < f2; i++) { V[i].push_front(vv); mp[i][vv]++; vv = *V[i].rbegin(); mp[i][vv]--; V[i].pop_back(); } mp[f2][valr]--; V[f2].erase(V[f2].begin() + s2); mp[f2][vv]++; V[f2].push_front(vv); } LL lans = 0; int decode(int x) { return (x + lans - 1)%n+1; } int ask(int l, int r, int k) { pair<int, int> pos1 = mark[l], pos2 = mark[r]; int f1 = pos1.first, s1 = pos1.second; int f2 = pos2.first, s2 = pos2.second; int cnt = 0; if(f1 == f2) { for(int i = s1; i <= s2; i++) if(V[f1][i] == k) cnt++; } else { for(int i = s1; i < V[f1].size(); i++) if(V[f1][i] == k) cnt++; for(int i = 0; i <= s2; i++) if(V[f2][i] == k) cnt++; for(int i = f1 + 1; i < f2; i++) cnt+=mp[i][k]; } return cnt; } void show() { for(int i = 1; i <= num; i++) for(int j =0; j < V[i].size(); j++) cout<<V[i][j]<<" "; puts(""); } int main() { scanf("%d", &n); build(); for(int i = 1; i <= n; i++) { int v; scanf("%d", &v); V[belong[i]].push_back(v); mark[i] = {belong[i], V[belong[i]].size()-1}; mp[belong[i]][v]++; } int q; scanf("%d", &q); for(int i = 1; i <= q; i++) { int c, u, v; scanf("%d%d%d", &c, &u, &v); u = decode(u), v = decode(v); if(u > v) swap(u, v); if(c == 1) { update(u, v); } else { int k; scanf("%d", &k); k = decode(k); lans = ask(u, v, k); printf("%d\n", lans); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-16465.html

最新回复(0)