商业十大网站,哈尔滨双城区建设局网站,外国网站后台设计,公众号编辑器下载P4135 作诗
题意#xff1a;
给定 n 个不大于 c 的正整数 a1…an 和 m 组询问#xff0c;每次问 [l,r] 中有多少个数出现正偶数次。 对于每次询问#xff1a; 设上一个询问的答案为 ans#xff08;第一个询问时 ans0#xff09;#xff0c;令L(lans)mod n1#xff0c;…P4135 作诗
题意
给定 n 个不大于 c 的正整数 a1…an 和 m 组询问每次问 [l,r] 中有多少个数出现正偶数次。 对于每次询问 设上一个询问的答案为 ans第一个询问时 ans0令L(lans)mod n1R(rans)mod n1若LR交换 L 和 R则本次询问为[L,R]。
题解
第一反应是莫队但是题目明确说了是强制在线 当这种区间问题想不到什么好方法时分块暴力就是最好的方法 首先预处理前i块内颜色为j的出现几次sum[i][j] ans[i][j]表示第i块到第j块内有多少数出现了偶数次 cnt[i]表示i颜色出现次数cnt每次用完都会清空 对于每次询问我们先求出大块内的数据以及每个数字出现个数然后加入左侧小块更新答案再加入右侧小块更新答案 其实就是很暴力很暴力的想法和做法只是利用分块优化了复杂度 更新cnt不要用memset直接for清空就行不然会超时 时间复杂度 n * sqrt(n) 空间复杂度 n * sqrt(n)
代码
这种题真正的写几遍才算明白我写了三四遍
#include bits/stdc.h
using namespace std;
const int MAX_N 100010;
const int MAX_M 330;
int n, m, siz, Ans;
int a[MAX_N], belong[MAX_N], cnt[MAX_N], sum[MAX_M][MAX_N], ans[MAX_M][MAX_M];//const int Size 1 16;int read()
{int x 0, f 1; char ch getchar();while (!isdigit(ch)) { if (ch -) f -1; ch getchar(); }while (isdigit(ch)) { x x * 10 ch - 0; ch getchar(); }return x * f;
}
int query(int x, int y)
{x (x Ans) % n 1, y (y Ans) % n 1;if (x y) swap(x, y);int l belong[x], r belong[y];Ans 0;if (r l 1)//在一个块或者相邻两个块内直接暴力 {for (int i x; i y; i){cnt[a[i]];if (!(cnt[a[i]] 1)) Ans;else if (cnt[a[i]] 2) --Ans;}for (int i x; i y; i) --cnt[a[i]];return Ans;}Ans ans[l 1][r - 1];//大块内有多少数出现了偶数次for (int i x; i l * siz; i)//左侧小块 {//加上左侧小块内的数据看有多少数出现了偶数次 cnt[a[i]];if (!((cnt[a[i]] sum[r - 1][a[i]] - sum[l][a[i]]) 1)) Ans;else if (cnt[a[i]] sum[r - 1][a[i]] - sum[l][a[i]] 2) --Ans;}for (int i (r - 1) * siz 1; i y; i)//右侧小块 {//同上 cnt[a[i]];if (!((cnt[a[i]] sum[r - 1][a[i]] - sum[l][a[i]]) 1)) Ans;else if (cnt[a[i]] sum[r - 1][a[i]] - sum[l][a[i]] 2) --Ans;}//---清零cnt数组 for (int i x; i l * siz; i) --cnt[a[i]];for (int i (r - 1) * siz 1; i y; i) --cnt[a[i]];return Ans;
}
int main()
{n read(), read(), m read();for (int i 1; i n; i) a[i] read();siz sqrt(n) 1;for (int i 1; i n; i){belong[i] (i - 1) / siz 1;sum[belong[i]][a[i]]; }for (int i 1; i MAX_N; i)for (int j 1; j belong[n]; j)sum[j][i] sum[j - 1][i];//前缀和 //sum[i][a[i]]前i个块内a[i]出现了几次 for (int i 1; i belong[n]; i)//第i块内 {int now 0;for (int j (i - 1) * siz 1; j n; j)//从第i块到最后内所有数的出现次数 {cnt[a[j]];if (!(cnt[a[j]] 1)) now;//出现偶数次 else if (cnt[a[j]] 2) --now;//出现奇数次就撤回 ans[i][belong[j]] now;//记录i到j块内有多少数出现了偶数次 }for (int j (i - 1) * siz 1; j n; j)//清空cnt不要用memset --cnt[a[j]]; }while (m--){int x read(), y read();printf(%d\n, query(x, y));}return 0;
}
