当前位置:网站首页>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;
}
边栏推荐
- Shell programming core technology "I"
- 2021 合肥市信息学竞赛小学组
- 整理混乱的头文件,我用include what you use
- Lenovo explains in detail the green smart city digital twin platform for the first time to solve the difficulties of urban dual carbon upgrading
- "Only one trip", active recommendation and exploration of community installation and maintenance tasks
- Lm10 cosine wave homeopathic grid strategy
- 876. Intermediate node of linked list
- There are multiple divs in the large div, which are displayed on the same line. After overflow, scroll bars are generated without line breaks
- mysql中explain语句查询sql是否走索引,extra中的几种类型整理汇总
- HDU 6440 2018中国大学生程序设计网络选拔赛
猜你喜欢
Opencv functions and methods related to binary threshold processing are summarized for comparison and use
Oracle with as ora-00903: invalid table name multi report error
Hough transform Hough transform principle
与二值化阈值处理相关的OpenCV函数、方法汇总,便于对比和拿来使用
使用canal配合rocketmq监听mysql的binlog日志
2022CoCa: Contrastive Captioners are Image-Text Fountion Models
欧拉函数
Use canal and rocketmq to listen to MySQL binlog logs
Pointnet/Pointnet++点云数据集处理并训练
关于判断点是否位于轮廓内的一点思考
随机推荐
性能优化之关键渲染路径
长城证券开户安全吗 买股票怎么开户
整理混乱的头文件,我用include what you use
测试工程师如何“攻城”(下)
在线文本行固定长度填充工具
《工作、消费主义和新穷人》的微信读书笔记
An example of multi module collaboration based on NCF
Safer, smarter and more refined, Chang'an Lumin Wanmei Hongguang Mini EV?
牛客小白月赛7 谁是神箭手
Is Guoyuan futures a regular platform? Is it safe to open an account in Guoyuan futures?
Cache é JSON uses JSON adapters
Shell 编程核心技术《二》
Lenovo explains in detail the green smart city digital twin platform for the first time to solve the difficulties of urban dual carbon upgrading
1003 Emergency(25 分)(PAT甲级)
The kth largest element in the array
Pointnet/Pointnet++点云数据集处理并训练
建立自己的网站(15)
Caché WebSocket
联想首次详解绿色智城数字孪生平台 破解城市双碳升级难点
One question per day (2022-07-02) - Minimum refueling times