作诗

C++14(g++5.4) 解法, 执行用时: 1748ms, 内存消耗: 15048K, 提交时间: 2020-05-27 12:26:23

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+10,T=1500+10;
int a[N],b[N],L[T],R[T],pos[N],f[T][T],cnt[N];
vector<int> e[N];
//预处理 

int find(int x,int l,int r) //二分查找第一个大于等于l的数，二分查找最后一个小于等于r的数，两者相减，得到x在[l,r]中出现的次数 
{
	return upper_bound(e[x].begin(), e[x].end(), r)-lower_bound(e[x].begin(), e[x].end(), l);
}

int ask(int l, int r) 
{ 
	int p=pos[l],q=pos[r];//p是l所属的块，q是r所属的块 
	int ans=f[p+1][q-1],tot=0;
	for(int i=l;i<=min(R[p],r);i++)
	{	
		if(!cnt[a[i]])b[++tot]=a[i];
		cnt[a[i]]++;
	}
	if(p!=q)
		for(int i=L[q];i<=r;i++)
		{
			if(!cnt[a[i]])b[++tot]=a[i];
			cnt[a[i]]++;
		}
	for(int i=1;i<=tot;i++)//头尾两端不完整区间里面的出现过的数字个数是tot 
	{
		int sum=find(b[i],l,r),sum1=sum-cnt[b[i]],sum2=cnt[b[i]];
		//sum是b[i]在l和r之间出现的次数,sum2是不完整区间里的出现次数,sum1是完整区间里的出现次数 
		//sum=sum1+sum2
		if(sum1&1)//奇数 
		{
			if(sum2&1)ans++;//奇数+奇数=偶数 
		}
		else if(sum1)//不是奇数但也不为0 
		{
			if(sum2&1)ans--;//奇数+偶数=奇数 
		}
		else//sum1是0 
		{
			if(!(sum2&1))ans++;//0+偶数=偶数 
		}
	}
	for(int i=l;i<=min(R[p],r);i++)cnt[a[i]]=0;
	for(int i=L[q];i<=r;i++)cnt[a[i]]=0;
	return ans;
}

int main() 
{
	int n,c,m;
	cin>>n>>c>>m;//长度为n,m个查询 
	for (int i=1;i<=n;i++)
	{
		scanf("%d", &a[i]);//读入原始数据
		e[a[i]].push_back(i);//按顺序保存该数值在序列a中每次出现的位置  
	}	
	int t=sqrt(log(n)/log(2)*n);//计算t 
	int len=t?n/t:n;//每段的长度 
	for(int i=1;i<=t;i++) 
	{
		L[i]=(i-1)*len+1;//第i段的左端点 
		R[i]=i*len;//第i段的右端点 
	}
	if(R[t]<n) //处理最后一段 
	{
		L[t+1]=R[t]+1;
		R[++t]=n;
	}
	for(int i=1;i<=t;i++)
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i;//记录第j个数属于哪一段 
	//预处理		
	memset(f,0,sizeof(f));
	for(int i=1;i<=t;i++) 
	{
		memset(cnt,0,sizeof(cnt));
		int tot=0;
		for(int j=L[i];j<=n;j++)
		{
			cnt[a[j]]++;
			if(cnt[a[j]]%2==1 and cnt[a[j]]!=1) tot--;//仅有一个数的时候不减少 
			if(cnt[a[j]]%2==0)tot++;
			f[i][pos[j]]=tot;
		}
	}
	int x=0;
	memset(cnt,0,sizeof(cnt));
	while (m--) 
	{
		int l, r;
		scanf("%d %d", &l, &r);
		l=(l+x)%n+1;
		r=(r+x)%n+1;
		if(l>r)swap(l,r);
		x=ask(l,r);
		printf("%d\n",x);
	}
	return 0;
}

C++ 解法, 执行用时: 3321ms, 内存消耗: 6700K, 提交时间: 2021-10-17 11:06:06

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, c, m, ans;
int cnt[N], a[N];
vector<int> fs[N];
int t, L[N], R[N], pos[N];
int dp[500][500];
int get(int l, int r, int v) {
	return upper_bound(fs[v].begin(), fs[v].end(), r) - upper_bound(fs[v].begin(), fs[v].end(), l - 1);
}
void pre() {
	cin >> n >> c >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		fs[a[i]].push_back(i);
	}
	t = sqrt(n);
	for (int i = 1; i <= t; i++) {
		R[i] = i * (n / t);
		L[i] = R[i - 1] + 1;
	}
	if (R[t] != n) R[++t] = n, L[t] = R[t - 1] + 1;
	for (int i = 1; i <= t; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
		}
	}
	for (int i = 1; i <= t; i++) {
		memset(cnt, 0, sizeof(cnt));
		int tot = 0;
		for (int j = L[i]; j <= n; j++) {
			cnt[a[j]]++;
			if (cnt[a[j]] >= 2) {
				if (cnt[a[j]] & 1) tot--;
				else tot++;
			}
			dp[i][pos[j]] = tot;
		}
	}
	memset(cnt, 0, sizeof(cnt));
}
void ask(int l, int r) {
	int p = pos[l], q = pos[r];
	ans = 0;
	int b[N], tol = 0;
	memset(cnt, 0, sizeof(cnt));
	if (p + 1 >= q) {
		for (int i = l; i <= r; i++) {
			cnt[a[i]]++;
			if (cnt[a[i]] >= 2) {
				if (cnt[a[i]] & 1) ans--;
				else ans++;
			}
		}

	} else {
		ans = dp[p + 1][q - 1];
		for (int i = l; i <= R[p]; i++) {
			if (!cnt[a[i]]) b[++tol] = a[i];
			cnt[a[i]]++;
		}
		for (int i = L[q]; i <= r; i++) {
			if (!cnt[a[i]]) b[++tol] = a[i];
			cnt[a[i]]++;
		}
		for (int i = 1; i <= tol; i++) {
			int sum1 = cnt[b[i]];
			int sum2 = get(L[p + 1], R[q - 1], b[i]);
			if (sum2 == 0) {
				if (sum1 >= 2) {
					if (sum1 & 1);
					else ans++;

				}
			} else {
				if (sum2 & 1) {
					if (sum1 & 1) ans++;

				} else {
					if (sum1 & 1) ans--;

				}
			}

		}
	}
}
void solve() {
	while (m--) {
		int l, r;
		cin >> l >> r;
		l = (l + ans) % n + 1;
		r = (r + ans) % n + 1;
		if (l > r) swap(l, r);
		ask(l, r);
		cout << ans << endl;
	}
}
int main( ) {
	pre();
	solve();
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 1148ms, 内存消耗: 12384K, 提交时间: 2022-08-09 12:31:30

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX_N=101000;
vector<int>v[MAX_N];
int a[MAX_N],num[MAX_N],sum[MAX_N];
int L[MAX_N],R[MAX_N],t;
int dp[1510][1510];
int pos[MAX_N]; 
int ask(int l,int r){
	int p=pos[l],q=pos[r];
	int ans=0,i,j;
	if(p==q){
		for(i=l;i<=r;i++){
			sum[a[i]]++;
			if(sum[a[i]]%2==0)
			ans++;
			else if(sum[a[i]]!=1)
			ans--;
		}
		for(i=l;i<=r;i++){
			sum[a[i]]--;
		}
	}
	else{
		ans+=dp[p+1][q-1];
		if(p+1!=q){
			for(i=l;i<=R[p];i++){
				if(sum[a[i]])
				continue;
				sum[a[i]]=upper_bound(v[a[i]].begin(),v[a[i]].end(),L[q]-1)-lower_bound(v[a[i]].begin(),v[a[i]].end(),R[p]+1);	
			}
			for(i=L[q];i<=r;i++){
				if(sum[a[i]])
				continue;
				sum[a[i]]=upper_bound(v[a[i]].begin(),v[a[i]].end(),L[q]-1)-lower_bound(v[a[i]].begin(),v[a[i]].end(),R[p]+1);	
			}
		}
		for(i=l;i<=R[p];i++){
			sum[a[i]]++;
			if(sum[a[i]]%2==0)
			ans++;
			else if(sum[a[i]]!=1)
			ans--;
		}
		for(i=L[q];i<=r;i++){
			sum[a[i]]++;
			if(sum[a[i]]%2==0)
			ans++;
			else if(sum[a[i]]!=1)
			ans--;
		}
		for(i=l;i<=R[p];i++)
		sum[a[i]]=0;
		for(i=L[q];i<=r;i++)
		sum[a[i]]=0;
	}
	return ans;
}
int main(void){
	int n,c,m,i,j,k,l,r;
	scanf("%d%d%d",&n,&c,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		v[a[i]].push_back(i);
	}
	t=sqrt(n*log(n));
	for(i=1;i<=t;i++){
		L[i]=(i-1)*(n/t)+1;
		R[i]=i*(n/t);
	}
	if(R[t]<n){
		t++;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for(i=1;i<=t;i++){
		for(j=L[i];j<=R[i];j++)
		pos[j]=i;
	}
	for(i=1;i<=t;i++){
		for(j=1;j<=c;j++)
		num[j]=0;
		int ans=0;
		for(j=i;j<=t;j++){
			for(k=L[j];k<=R[j];k++){
				num[a[k]]++;
				if(num[a[k]]%2==0)
				ans++;
				else if(num[a[k]]!=1)
				ans--;
			}
			dp[i][j]=ans;
		}
	}
	int res=0;
	for(i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		l=(l+res)%n+1;
		r=(r+res)%n+1;
		if(l>r)
		swap(l,r);
		res=ask(l,r);
		printf("%d\n",res);
	}
	return 0;
}

详情