description

在线询问区间内出现次数为正偶数的数的种数。

data range

\[n,m\le 10^5
\]

solution

分块大法好

首先离散化权值

这种对于权值做询问并且询问放在一起的分块其实很好做

我们首先预处理出以下两个东西:

1:\(s[i][j]\),表示前\(i\)个块内权值为\(j\)的数的个数,这个预处理是\(O(n\sqrt n)\)的

2:\(w[i][j]\),表示第\(i\)个块到第\(j\)个块内我们要查询的信息,

这个我们每次从\(\sqrt n\)个块的块头开始扫一边数组即可,复杂度为\(O(n\sqrt n)\)

查询的时候,首先调用\(w[i][j]\)调用整体块内的信息

对于两边的\(2\sqrt n\)个数,我们可以使用桶+查询整体块内对应权值来获取对应最多\(2\sqrt n\)个权值的信息

于是我们就用时间和空间复杂度均为\(O(n\sqrt n)\)的分块解决了这种题目

Code

#include<bits/stdc++.h>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<complex>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<ctime>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define Cpy(x,y) memcpy(x,y,sizeof(x))

#define Set(x,y) memset(x,y,sizeof(x))

#define FILE "2821"

#define mp make_pair

#define pb push_back

#define RG register

#define il inline

using namespace std;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

const int N=100010;

const int M=10000010;

const dd eps=1e-5;

const int inf=2147483647;

const ll INF=1ll<<60;

const ll P=100000;

il ll read(){

  RG ll data=0,w=1;RG char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

  if(ch=='-')w=-1,ch=getchar();

  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

  return data*w;

}

il void file(){

  srand(time(NULL)+rand());

  freopen(FILE".in","r",stdin);

  freopen(FILE".out","w",stdout);

}

int n,c,Q,m,blk,len,o[N],a[N],b[N],s[352][N],w[352][352],t[N],ans;

int main()

{

  n=read();c=read();Q=read();m=350;blk=(n-1)/m+1;

  for(RG int i=1;i<=n;i++){o[i]=a[i]=read();b[i]=(i-1)/m+1;}

  sort(o+1,o+n+1);len=unique(o+1,o+n+1)-o-1;

  for(RG int i=1;i<=n;i++)a[i]=lower_bound(o+1,o+len+1,a[i])-o;

  for(RG int i=1;i<=blk;i++){

    for(RG int j=1;j<=len;j++)s[i][j]=s[i-1][j];

    for(RG int j=(i-1)*m+1;j<=n&&j<=i*m;j++)s[i][a[j]]++;

    memset(t,0,sizeof(t));ans=0;

    for(RG int j=i;j<=blk;w[i][j]=ans,j++)

      for(RG int k=(j-1)*m+1;k<=n&&k<=j*m;k++){

	t[a[k]]++;if(t[a[k]]>=2)(t[a[k]]&1)?ans--:ans++;

      }

  }

  ans=0;

  while(Q--){

    RG int l=(read()+ans)%n+1,r=(read()+ans)%n+1;if(l>r)swap(l,r);

    if(b[l]==b[r]){

      ans=0;

      for(RG int i=l;i<=r;i++)t[a[i]]=0;

      for(RG int i=l;i<=r;i++){

	t[a[i]]++;if(t[a[i]]>=2)(t[a[i]]&1)?ans--:ans++;

      }

    }

    else{

      for(RG int i=l;i==l||i%m!=1;i++)t[a[i]]=0;

      for(RG int i=r;i==r||i%m!=0;i--)t[a[i]]=0;

      ans=w[b[l]+1][b[r]-1];

      for(RG int i=l,ret;i==l||i%m!=1;i++){

	if(!t[a[i]])t[a[i]]+=(s[b[r]-1][a[i]]-s[b[l]][a[i]]);

	t[a[i]]++;ret=t[a[i]];

	if(ret>=2)(ret&1)?ans--:ans++;

      }

      for(RG int i=r,ret;i==r||i%m!=0;i--){

	if(!t[a[i]])t[a[i]]+=(s[b[r]-1][a[i]]-s[b[l]][a[i]]);

	t[a[i]]++;ret=t[a[i]];

	if(ret>=2)(ret&1)?ans--:ans++;

      }

    }

    printf("%d\n",ans);

  }

  return 0;

}

巴特西

[BZOJ2821]作诗

description

data range

solution

Code

最新文章

热门文章