目录
codeforces 260D Serega and Fun题意：题解：Code:
codeforces 260D Serega and Fun
题目传送们
题意：
给出长度为\(n\)的序列，要求支持两种操作： 1.将\([l,r]\)区间的数循环右移一位。 2.询问\([l,r]\)区间的数中等于\(k\)的个数。 一共\(q\)次操作，要求对于每一个询问进行回答，并且强制在线。\((1 \leq n,q \leq 10^5 , 1 \leq a_i \leq n)\)
题解：
由于之前写过了\(ORZJRY\) \(I\)，然后那题里面也有一个循环位移的操作，于是就想到了用块状链表来写这道题目了...（我才不会说我第一个想到的是树套树）对于循环位移的操作，我们是很好处理的，但是对于询问，我们则需要思考一下了。如果用map存的话，每次更新块内信息是\(log(n)\)的，查询也是\(log(n)\)的，如果用数组存下来的话，每次暴力更新块内信息则是\(log(n)\)的，查询则可以做到\(O(1)\)，实际上都不怎么优秀。但仔细想想会发现它的操作实际上只是循环右移一位，所以对于最左边和最右边的两个块，每次位移都只有一个元素会进行更新，所以只需要更新这一个元素即可。然后自己的块状链表写完之后发现并不需要\(Split\)和\(Merge\)操作了，反而更像一个分块。。不过跑的还挺快，记得根号次位移之后重构一下块防止被卡。
Code:
#pragma GCC optimize (2,"inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
#define fi first
#define se second
int Blocksz;
int n,q,c,ans;
int temp[200650],a[200650];
/*==================Define Area================*/
namespace BlockList {
struct node {
int tmp[850],cnt[100050];
int sz,nxt;
}t[505];
queue<int>Q;
void Clear(int o) {t[o].sz=0;}
void Del(int o) {Q.push(o);Clear(o);}
int Newnode() {assert(Q.size());int id=Q.front();Q.pop();return id;}
void Init() {for(int i=1;i<=500;i++) Q.push(i);t[0].nxt=-1,t[0].sz=0;}
void Debug() {
int tot=0;
for(int i=0;~i;i=t[i].nxt) {
printf("sequence %d:",i);
for(int j=1;j<=t[i].sz;j++) {
printf("%d ",t[i].tmp[j]);
}
tot++;
printf(" nxt: %d ",t[i].nxt);
puts("");
}
puts("");
cerr<< "totblock:" << tot << endl;
}
void Find(int &pos,int &now) {
for (now=0;t[now].nxt!=-1&&pos>t[now].sz;now=t[now].nxt)
pos-=t[now].sz;
}
void Insert(int *a) {
int nownd=0;
for(int i=1;i<=n;i++) {
if(t[nownd].sz<Blocksz) {
++t[nownd].sz;
t[nownd].tmp[t[nownd].sz]=a[i];
t[nownd].cnt[a[i]]++;
}
else {
int nd=Newnode();
t[nd].nxt=t[nownd].nxt;
t[nownd].nxt=nd;
nownd=nd;
++t[nownd].sz;
t[nownd].tmp[t[nownd].sz]=a[i];
t[nownd].cnt[a[i]]++;
}
}
}
void Move(int l,int r) {
int lpos=0,rpos=0;
Find(l,lpos);Find(r,rpos);
int Turn=t[rpos].tmp[r];
if(lpos==rpos) {
for(int i=r;i>l;i--) {
t[lpos].tmp[i]=t[lpos].tmp[i-1];
}
t[lpos].tmp[l]=Turn;
return ;
}
t[rpos].cnt[Turn]--;
for(int i=r;i<t[rpos].sz;i++) {
t[rpos].tmp[i]=t[rpos].tmp[i+1];
}
t[rpos].sz--;
t[lpos].sz++;
for(int i=t[lpos].sz;i>l;i--) {
t[lpos].tmp[i]=t[lpos].tmp[i-1];
}
t[lpos].cnt[Turn]++;
t[lpos].tmp[l]=Turn;
}
int Getcnt(int l,int r,int num) {
int lpos=0,rpos=0;
int res=0;
Find(l,lpos);Find(r,rpos);
if(lpos==rpos) {
for(int i=l;i<=r;i++) {
if(t[lpos].tmp[i]==num) {
res++;
}
}
return res;
}
for(int i=l;i<=t[lpos].sz;i++) if(t[lpos].tmp[i]==num) res++;
for(int i=1;i<=r;i++) if(t[rpos].tmp[i]==num) res++;
for(int i=t[lpos].nxt;i!=rpos;i=t[i].nxt) {
res+=t[i].cnt[num];
}
return res;
}
void Rebuild() {
int nw=0;
for(int i=0;~i;i=t[i].nxt) {
for(int j=1;j<=t[i].sz;j++) {
temp[++nw]=t[i].tmp[j];
t[i].cnt[t[i].tmp[j]]--;
}
}
for(int i=t[0].nxt;~i;) {
t[i].sz=0;Q.push(i);
int now=i;
i=t[i].nxt;
t[now].nxt=-1;
}
t[0].nxt=-1;t[0].sz=0;
Insert(temp);
return ;
}
}
using namespace BlockList;
int main() {
read(n);
Blocksz=420;
Init();
for(int i=1;i<=n;i++) {
read(a[i]);
}
Insert(a);
read(q);
while(q--) {
int opt;
read(opt);
if(opt==1) {
int l,r;
read(l);read(r);
l=(l+ans-1)%n+1;
r=(r+ans-1)%n+1;
if(l>r) swap(l,r);
Move(l,r);
c++;
}
if(opt==2) {
int l,r,k;
read(l);read(r);read(k);
l=(l+ans-1)%n+1;
r=(r+ans-1)%n+1;
k=(k+ans-1)%n+1;
if(l>r) swap(l,r);
ans=Getcnt(l,r,k);
printf("%d\n",ans);
}
if(c==Blocksz) {
Rebuild();
c=0;
}
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9845426.html
相关资源：JAVA上百实例源码以及开源项目
