分块题单¶
成双成对¶
内存限制：256 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
题目描述
美汁汁作为一个强迫症患者，喜欢看到东西成双成对地出现。如今有一个长度为n的序列A1An。已知美汁汁向这个序列看了m眼，第i眼看到的坐标的范围是liri。请问每一次看到的数中有多少种数是出现了偶数次。
输入第一行三个整数n、c以及m。表示序列长度、Ai的种类数、询问数。第二行有n个整数，每个数在[1, c]间，代表Ai。接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，
令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。
输出共m行，每行一个整数，第i个数表示第i次有多少种数字出现偶数次。
预处理cnt_{i,j}为前i块中j出现的次数，f_{i,j}为第[i,j]块的答案。
// Problem: G. 成双成对
// Contest: LibreOJ - S
// URL: http://www.nfls.com.cn:20035/contest/2100/problem/7
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#pragma GCC optimize(2)
#pragma GCC target("avx") // AVX指令集(不懂的去问度娘)
#pragma GCC optimize(1) // o1优化
#pragma GCC optimize(2) // o2优化
#pragma GCC optimize(3) // o3优化
#pragma GCC optimize("Ofast") // ofast优化(优化到破坏标准合规性的点)，
#pragma GCC optimize("inline") // inline中和
#pragma GCC optimize("-fgcse") // fgcse优化
#pragma GCC optimize("-fgcse-lm") //-fgcse-lm
#pragma GCC optimize("-fipa-sra") //除换
#pragma GCC optimize("-ftree-pre") //快速tree
#pragma GCC optimize("-ftree-vrp") //去重tree
#pragma GCC optimize("-fpeephole2") // flatco2优化
#pragma GCC optimize("-ffast-math") //数论优化
#pragma GCC optimize("-fsched-spec") //富硒优化
#pragma GCC optimize("unroll-loops") //图论plus优化
#pragma GCC optimize("-falign-jumps") //极优化
#pragma GCC optimize("-falign-loops") //图论重+排除
#pragma GCC optimize("-falign-labels") // lamb优化
#pragma GCC optimize("-fdevirtualize") // fugechar优化
#pragma GCC optimize("-fcaller-saves") //负优化排除
#pragma GCC optimize("-fcrossjumping") //极优化p+
#pragma GCC optimize("-fthread-jumps") //多重极优化
#pragma GCC optimize( \
"-funroll-loops") //消除分支可以减少预测的可能性能：比如小的循环可以展开比如循环次数小于64次（可以使用GCC选项
//-funroll-loops)
#pragma GCC optimize("-fwhole-program") //弗洛伊德优化
#pragma GCC optimize("-freorder-blocks") //半刻优化
#pragma GCC optimize("-fschedule-insns") // fschedule-insns优化
#pragma GCC optimize("inline-functions") // inline-functions优化
#pragma GCC optimize("-ftree-tail-merge") //-ftree-tail-merge优化
#pragma GCC optimize("-fschedule-insns2") //-fschedule-insns2优化
#pragma GCC optimize("-fstrict-aliasing") //-fstrict-aliasing优化
#pragma GCC optimize("-fstrict-overflow") //不知道
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma G++ target("avx")
#pragma G++ optimize(1)
#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#pragma G++ optimize("-fstrict-overflow") //不知道
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-fhoist-adjacent-loads")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
// #define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
inline int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=1e5+5;
const ull P=137;
// const int INF=1e18+7;
/*
策略
*/
const int B=180;
int cnt[605][N];
int cc[N];
int a[N];
int ans[605][605];
inline int query(int l,int r){
if(l>r)l^=r^=l^=r;
int lb=l/B,rb=r/B;
// cdbg(l,r,lb,rb);
int res=0;
if(l/B==r/B){
for(int i=l;i<=r;i++){
cc[a[i]]++;
if(cc[a[i]]>1){if(cc[a[i]]%2)res--;else res++;}
}
for(int i=l;i<=r;i++){
cc[a[i]]--;
}
return res;
}
// #define cur (((rb-1>=0)?(cnt[rb-1][a[i]]-cnt[lb][a[i]]):0)+cc[a[i]])
res=ans[lb+1][rb-1];
int lim=(l/B+1)*B;
for(int i=l;i<lim;i++){
cc[a[i]]++;
int cur=(((rb-1>=0)?(cnt[rb-1][a[i]]-cnt[lb][a[i]]):0)+cc[a[i]]);
if(!(cur&1))res++;
else if(cur^1)res--;
}
for(int i=r/B*B;i<=r;i++){
cc[a[i]]++;
int cur=(((rb-1>=0)?(cnt[rb-1][a[i]]-cnt[lb][a[i]]):0)+cc[a[i]]);
if(!(cur&1))res++;
else if(cur^1)res--;
}
for(int i=l;i<lim;i++){
cc[a[i]]--;
}
for(int i=r/B*B;i<=r;i++){
cc[a[i]]--;
}
return res;
}
signed main(){
int n=rd,c=rd,m=rd;
for(int i=0;i<n;i++){
a[i]=rd;
cnt[i/B][a[i]]++;
}
int mxb=(n-1)/B;
for(int i=0;i<=mxb;i++){
for(int j=1;j<=c;j++){
if(i>0)cnt[i][j]+=cnt[i-1][j];
}
}
for(int i=0;i<=mxb;i++){
for(int j=i;j<=mxb;j++){
if(j>0)ans[i][j]=ans[i][j-1];
int lim=min((j+1)*B,n);
for(int k=j*B;k<lim;k++){
if(!(++cc[a[k]]&1))ans[i][j]++;
else if(cc[a[k]]^1)ans[i][j]--;
}
}
for(int i=1;i<=c;i++)cc[i]=0;
}
int lstans=0;
while(m--){
int l=(rd+lstans)%n,r=(rd+lstans)%n;
printf("%d\n",(lstans=query(l,r)));
}
return 0;
}
Lucky¶
WLD总是运气很好，他的幸运数字是k。k是一个奇数。 他现在碰到了一个陌生人，陌生人带了n个数字\(a_1,a_2,...,a_n\)。陌生人问了他m个问题，每个问题形如： 给定两个区间\([l_i,r_i]\)和\([u_i,v_i]\)，你可以从\([l_i,r_i]\)里选择一个数x，\([u_i,v_i]\)里选择一个数y，问组合(x,y)有多少种满足\(a_x+a_y=k\) 如果WLD可以正确回答所有问题，他就是全世界最幸运的人了，你能帮他吗？
一个询问可以看成问一个矩形内符合条件的点。将询问进一步划分为4个二维前缀和。预处理f_{i,j}为前i块和前块的匹配数。于是就可以回答。
// Problem: F. Lucky
// Contest: LibreOJ - S
// URL: http://www.nfls.com.cn:20035/contest/2100/problem/6
// Memory Limit: 64 MB
// Time Limit: 6000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
// #define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
int n,v[N],cnt[202][30001];
int f[202][202];
int B=200;
int ccnt[30001];
int K;
int query(int a,int b){
if(a<0||b<0)return 0;
// cdbg(a+1,b+1);
int res=0;
if(a/B>0&&b/B>0)res+=f[a/B-1][b/B-1];
for(int i=a/B*B;i<=a;i++){
ccnt[v[i]]++;
}
for(int i=b/B*B;i<=b;i++){
if(v[i]<=K&&K-v[i]<=30000)res+=ccnt[K-v[i]]+(a/B>0?cnt[a/B-1][K-v[i]]:0);
}
for(int i=a/B*B;i<=a;i++){
ccnt[v[i]]--;
}
// cdbg(res);
// for(int i=b/B*B;i<=b;i++){ 别重复了
// ccnt[v[i]]++;
// }
//
for(int i=a/B*B;i<=a;i++){
if(v[i]<=K&&K-v[i]<=30000)res+=(b/B>0?cnt[b/B-1][K-v[i]]:0);
}
// for(int i=b/B*B;i<=b;i++){
// ccnt[v[i]]++;
// }
return res;
}
void solve(){
K=rd;
memset(cnt,0,sizeof cnt);
memset(f,0,sizeof f);
for(int i=0;i<n;i++)v[i]=rd;
for(int i=0;i<n;i++){
cnt[i/B][v[i]]++;
}
int mxb=(n-1)/B;
for(int i=0;i<=mxb;i++){
for(int j=1;j<=30000;j++){
if(i>0)cnt[i][j]+=cnt[i-1][j];
}
}
for(int i=0;i<=mxb;i++){
for(int j=0;j<=mxb;j++){
if(j>0)f[i][j]+=f[i][j-1];
for(int k=j*B;k<j*B+B;k++){
if(v[k]<=K&&K-v[k]<=30000)f[i][j]+=cnt[i][K-v[k]];
}
}
}
int m=rd;
while(m--){
int a=rd-1,x=rd-1,b=rd-1,y=rd-1;
printf("%d",query(x,y)-query(a-1,y)-query(x,b-1)+query(a-1,b-1));puts("");
}
}
signed main(){
while(scanf("%d",&n)!=EOF){
solve();
}
}