当前位置:网站首页>Educational Codeforces Round 22 E. Army Creation
Educational Codeforces Round 22 E. Army Creation
2022-07-04 18:01:00 【不吃土司边】
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
using namespace std;
#define X first
#define Y second
#define eps 1e-2
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;
const int N = 1e5+2;
const int INF = 1<<30;
const int mod = 1e9+7;
std::vector<int> v[N];
struct node{
int l,r,sum;
}t[N<<5];
int tot=0;
int build(int p,int l,int r){
p=++tot;
if(l==r) return p;
int mid=(l+r)>>1;
t[p].l=build(p,l,mid);
t[p].r=build(p,mid+1,r);
return p;
}
int update(int p,int l,int r,int x){
t[++tot]=t[p];p=tot;t[p].sum++;
if(l==r) return p;
int mid=(l+r)>>1;
if(x<=mid) t[p].l=update(t[p].l,l,mid,x);
else t[p].r=update(t[p].r,mid+1,r,x);
return p;
}
int query(int p1,int p2,int l,int r,int from,int to){
if(from<=l&&to>=r) return t[p2].sum-t[p1].sum;
int mid=(l+r)>>1,ans=0;
if(from<=mid) ans+=query(t[p1].l,t[p2].l,l,mid,from,to);
if(to>=mid+1) ans+=query(t[p1].r,t[p2].r,mid+1,r,from,to);
return ans;
}
int n,k,a[N],q,rt[N];
void solve(){
scanf("%d%d",&n,&k);rt[0]=build(1,0,n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]),v[a[i]].push_back(i);
int sz=v[a[i]].size();
int pos=(sz>k?v[a[i]][sz-1-k]:0);
rt[i]=update(rt[i-1],0,n,pos);
}
// cout<<tot<<endl;
scanf("%d",&q);
int last=0;
// cout<<t[18].sum<<endl;
// cout<<rt[1]<<" "<<rt[2]<<endl;
while(q--){
int l,r;scanf("%d%d",&l,&r);
l=((l+last)%n)+1;
r=((r+last)%n)+1;
if(l>r) swap(l,r);
// cout<<l<<" "<<r<<endl;
last=query(rt[l-1],rt[r],0,n,0,l-1);
cout<<last<<endl;
}
return;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
int t = 1;
//scanf("%d",&t);
while(t--){
// printf("Case %d: ",cas++);
solve();
}
return 0;
}
边栏推荐
- SSRS筛选器的IN运算(即包含于)用法
- Explore the contour drawing function drawcontours() of OpenCV in detail with practical examples
- FPGA timing constraint sharing 01_ Brief description of the four steps
- Stream流
- Jetpack Compose 教程
- Nebula importer data import practice
- How to use async Awati asynchronous task processing instead of backgroundworker?
- How test engineers "attack the city" (Part I)
- Caché WebSocket
- 大佬们,求助一下,我用mysql cdc 2.2.1(flink 1.14.5)写入kafka,设置
猜你喜欢
[发布] 一个测试 WebService 和数据库连接的工具 - DBTest v1.0
"Only one trip", active recommendation and exploration of community installation and maintenance tasks
Opencv functions and methods related to binary threshold processing are summarized for comparison and use
使用canal配合rocketmq监听mysql的binlog日志
Build your own website (15)
node_exporter部署
Explore the contour drawing function drawcontours() of OpenCV in detail with practical examples
To sort out messy header files, I use include what you use
FPGA timing constraint sharing 01_ Brief description of the four steps
Lm10 cosine wave homeopathic grid strategy
随机推荐
FTP, SFTP file transfer
876. 链表的中间结点
Detailed explanation of the binary processing function threshold() of opencv
从实时应用角度谈通信总线仲裁机制和网络流控
PointNeXt:通过改进的模型训练和缩放策略审视PointNet++
读写关闭的channel是啥后果?
1005 Spell It Right(20 分)(PAT甲级)
【问题】druid报异常sql injection violation, part alway true condition not allow 解决方案
Nebula importer data import practice
Shell 编程核心技术《一》
1672. Total assets of the richest customers
SSL证书续费相关问题详解
勾股数规律(任意三个数能够满足勾股定理需要满足的条件)
Unity给自己的脚本添加类似编辑器扩展的功能案例ContextMenu的使用
更安全、更智能、更精致,长安Lumin完虐宏光MINI EV?
BI技巧丨权限轴
Wireshark网络抓包
2014 Hefei 31st youth informatics Olympic Games (primary school group) test questions
欧拉函数
《看完就懂系列》字符串截取方法substr() 、 slice() 和 substring()之间的区别和用法