bzoj 2821 作诗 分块
2024-10-13 20:06:38
基本思路和蒲公英一样
还是预处理出每两个块间的答案
询问时暴力跑两边的贡献
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<ctime>
#include<algorithm>
#define N 100005
using namespace std;
int n,m,c,nn,tot,a[N],be[N],f[4000][4000],tim[N];
bool bo[N],flag[N];
vector <int> q[N];
void init(){
int ans;
for(int i=1;i<=tot;i++){
memset(bo,0,sizeof bo); ans=0;
memset(flag,0,sizeof flag);
for(int j=(i-1)*nn+1;j<=n;j++){
if(!flag[a[j]]){
flag[a[j]]=1; bo[a[j]]=1;
}
else{
if(!bo[a[j]]){bo[a[j]]=1;ans--;}
else{bo[a[j]]=0;ans++;}
}
if(!(j%nn)||j==n) f[i][be[j]]=ans;
}
}
}
int getnum(int l,int r,int x){
return upper_bound(q[x].begin(),q[x].end(),r)-lower_bound(q[x].begin(),q[x].end(),l);
}
int query(int l,int r,int ii){
int ans=0,t,tt;
if(be[l]==be[r]){
for(int i=l;i<=r;i++){
if(tim[a[i]]!=ii){
tim[a[i]]=ii;
t=getnum(l,r,a[i]);
if(t>0&&(!(t&1))) ans++;
}
}
return ans;
}
ans=f[be[l]+1][be[r]-1];
for(int i=l;i<=be[l]*nn;i++){
if(tim[a[i]]!=ii){
tim[a[i]]=ii;
t=getnum(l,r,a[i]);
tt=getnum(be[l]*nn+1,(be[r]-1)*nn,a[i]);
if(t!=0){
if((tt==0)&&(!(t&1))) ans++;
else if(tt!=0&&(1&t)!=(1&tt)){
if((t&1)) ans--;
else ans++;
}
}
}
}
for(int i=(be[r]-1)*nn+1;i<=r;i++){
if(tim[a[i]]!=ii){
tim[a[i]]=ii;
t=getnum(l,r,a[i]);
tt=getnum(be[l]*nn+1,(be[r]-1)*nn,a[i]);
if(t!=0){
if((tt==0)&&(!(t&1))) ans++;
else if(tt!=0&&(1&t)!=(1&tt)){
if((t&1)) ans--;
else ans++;
}
}
}
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&c,&m);
nn=(int)(n/(sqrt(8*m*log2(n))));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
be[i]=(i-1)/nn+1;
q[a[i]].push_back(i);
}
tot=be[n]; init();
//printf("%0.2lf\n",(double)clock()/CLOCKS_PER_SEC);
int ans=0,l,r;
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
l=(l+ans)%n+1;
r=(r+ans)%n+1;
if(l>r) swap(l,r);
ans=query(l,r,i);
printf("%d\n",ans);
}
return 0;
}
最新文章
- Android之常见问题集锦Ⅰ
- 【python】发送post请求
- 剑指Offer面试题：23.二叉树中和为某一值的路径
- Session Sticky About Nginx
- POJ 1113 - Wall 凸包
- Kafka简要图解
- SecureCRT 无法删除字符
- Entity Framework基金会
- 一次花费了一两个小时的mysql问题排查
- 一篇搞定微信分享和line分享
- layer ui插件显示tips时，修改字体颜色
- Leetcode_128_Longest Consecutive Sequence
- 强大而灵活的字体图标替代库iconfont
- TCP/UDP 常用端口列表
- bzoj 2563 [2012国家集训队Round 1 day2] 阿狸和桃子的游戏 贪心
- 编译64位cu文件的设置
- js 数组清空 方法 汇总
- LeetCode31.下一个排列 JavaScript
- 图灵杯 E 简单的RMQ（UVA 11235）（RMQ）
- Java的输入/输出操作