NC222521. AliceandBob
描述
输入描述
第一行，三个正整数，分别表示序列长度，游戏轮数，常数K。
接下来一行，n个整数，第i个表示。
接下来m行，每行2个整数，表示加密后的
。
保证
：
其中表示第i轮游戏的答案，定义
；
表示二进制的"异或"运算。
输出描述
总共m行，每行一个整数，表示有多少个连续子区间满足连续子区间中不同的数的个数不小于K。
示例1
输入:
6 3 3 1 2 1 3 2 1 0 5 11 9 2 5
输出:
9 0 3
C++ 解法, 执行用时: 99ms, 内存消耗: 5752K, 提交时间: 2021-06-07 17:18:58
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,m,k;
ll f[N],a[N],sum[N];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=n+2;
map<int,int>mm;
for(int i=1,j=1;j<=n;j++)
{
mm[a[j]]++;
while(mm.size()==k)
{
f[i]=j;
mm[a[i]]--;
if(mm[a[i]]==0)mm.erase(a[i]);
i++;
}
}
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+f[i];
ll ans=0;
while(m--)
{
ll L1,R1,L,R;
scanf("%lld%lld",&L1,&R1);
L=min(L1^ans,R1^ans)+1;
R=max(L1^ans,R1^ans)+1;
int pos=upper_bound(f+L,f+R+1,R)-f;
pos--;
ans=1ll*(pos-L+1)*(R+1)-(sum[pos]-sum[L-1]);
printf("%lld\n",ans);
}
return 0;
}
/*
R-f[l]+1
R-f[l+1]+1
.....
f[i]>R
*/