CF455D Serega and Fun(分块+deque)

简介: CF455D Serega and Fun(分块+deque)

原题链接

题意:

给定长度为N(N<=100000)的序列,支持两种操作:

1 l r 将区间l到r依次向右移动一位,a[r]移动到 [l]

2 l r k 询问区间l到r中k出现次数。

强制在线

思路:

考虑操作1对操作2的影响,分块后每次移动的时候,只有首项跟尾项元素会对答案产生影响。对每个块多加个deque维护一下。

由于1 < = a i < = n,对每个数都记录一下出现的次数,还要维护c [ i ] [ j ]表示第i块里j出现的次数;

更新的时候,注意处理整块与非整块的关系

代码:

// Problem: CF455D Serega and Fun
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF455D
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
typedef pair<double, double>PDD;
#define I_int ll
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void out(ll x){
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
inline void write(ll x){
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
#define read read()
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
ll ksm(ll a, ll b,ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)res = res * a%p ;
        a = a * a %p;
        b >>= 1;
    }
    return res;
}
const int inf = 0x3f3f3f3f;
const int maxn=1e5+7,maxm=210000;
int n,c[360][maxn];
deque<int>a[maxn];
int num,block,belong[maxn],l[maxn],r[maxn];
int ans=0;
void cul(int &x){
  x=(x+ans-1)%n+1;
}
void update(int l,int r){
  int bl=l/block,br=r/block;
  if(bl==br){
    r=r%block-1;
    int x=a[br][r];
    a[br].erase(a[br].begin()+r);
    a[bl].insert(a[bl].begin()+l%block,x);
  }
  else{
    int x;
    for(int i=bl;i<br;){
      x=a[i].back();a[i].pop_back();c[i][x]--;
      i++;
      a[i].push_front(x);c[i][x]++;
    }
    r%=block;x=a[br][r];
    a[br].erase(a[br].begin()+r);c[br][x]--;
    a[bl].insert(a[bl].begin()+l%block,x);c[bl][x]++;
  }
}
int query(int l,int r,int k){
  int an=0;
  int bl=l/block,br=r/block;
  if(bl==br){
    for(int i=l%block;i<r%block;i++)
      if(a[bl][i]==k) an++;
  }
  else{
    for(int i=bl+1;i<br;i++)
      an+=c[i][k];
    for(int i=l%block;i<a[i].size();i++)
      if(a[bl][i]==k) an++;
    for(int i=0;i<r%block;i++)
      if(a[br][i]==k) an++;
  }
  return an;
}
int main(){
  n=read;
  block=int(sqrt(n));
  rep(i,0,n-1){
    int x=read;
    a[i/block].push_back(x);
    c[i/block][x]++;
  }
  int q=read;
  while(q--){
    int op=read,l=read,r=read;
    cul(l);cul(r);
    if(l>r) swap(l,r);
    l--;
    if(op==1) update(l,r);
    else{
      int k=read;cul(k);
      ans=query(l,r,k);
      printf("%d\n",ans);
    }
  } 
  return 0;
}
目录
打赏
0
0
0
0
108
分享
相关文章
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。
ArrayList集合常用方法,.set可以用来生成图片和赋值命名,array.remove(1),array.set(1,“xxxx”)可以修改指定位置,array.size可以获取元素的个数
ArrayList集合常用方法,.set可以用来生成图片和赋值命名,array.remove(1),array.set(1,“xxxx”)可以修改指定位置,array.size可以获取元素的个数
C++:map&set 对红黑树的封装
C++:map&set 对红黑树的封装
62 1
|
9月前
|
【C++ map结构 】std::map 和 std::unordered_map 在使用上的差异
【C++ map结构 】std::map 和 std::unordered_map 在使用上的差异
166 0
用红黑树封装实现map和set
用红黑树封装实现map和set
50 0
|
9月前
使用Lamda表达式、stream流遍历Map、list
使用Lamda表达式、stream流遍历Map、list
167 0
C++中Vector/Map/List中尽量使用指针,避免直接保存对象
C++中Vector/Map/List中尽量使用指针,避免直接保存对象
519 0
【C 语言】数组 ( 多维数组做函数形参退化为指针过程 | int array[2][3] -> int array[][3] -> int (*array)[3] )
【C 语言】数组 ( 多维数组做函数形参退化为指针过程 | int array[2][3] -> int array[][3] -> int (*array)[3] )
180 0
【C 语言】数组 ( 多维数组做函数形参退化为指针过程 | int array[2][3] -> int array[][3] -> int (*array)[3] )
【C 语言】数组 ( 指针退化验证 | 计算数组大小 | #define LENGTH(array) (sizeof(array) / sizeof(*array)) )
【C 语言】数组 ( 指针退化验证 | 计算数组大小 | #define LENGTH(array) (sizeof(array) / sizeof(*array)) )
231 0
【C 语言】数组 ( 指针退化验证 | 计算数组大小 | #define LENGTH(array) (sizeof(array) / sizeof(*array)) )
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等