今天补题,补到一道块状链表裸题,然后苦逼的调了一天…….

题意:(这是道内部题目,不能透露…)

给你一串数字,然后支持两种操作
1. 给出l,r,然后轮换l\to r内的数字….
例子:现在有a_l,a_{l+1},a_{l+2}…..a_r,操作一次以后变成a_r,a_l,a_{l+1},a_{l+2}…..a_{r-1}
2. 询问l\to r区间内有多少个数字值为k

分析:

一看这道题目,看到区间轮换什么的,秒解分块可以做,用的是可以支持单点插入,单点修改的块状链表….对于每一个块,维护一个数组表示一个数字出现多少遍,(因为数字大小小于10^5),然后我们维护块状链表,每次调到那个链再跳到目标点,然后我们还要维护重构和删除…..就好了,细节贼多,而且数据有锅,最后特判过了…..
对于实现上,有问题可以问我,然后如果你看得懂我的代码…..想必是个神仙…..

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL inf=0x3f3f3f3f;
const LL N=1e5+10;
const LL mod=1e9+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,k,tot=1;
struct Node{int next,cost;} node[N];
struct Top{int next,to,siz;int Map[N];} top[900];
int Delete(int nod)
{
    int now=1,sum=0,ret;
    while(sum+top[now].siz<nod) 
        sum+=top[now].siz,now=top[now].next;
    int block_nod=now,flag=0;now=top[now].to;
    while(nod-sum-flag>2) flag++,now=node[now].next;
    if(nod-sum==1)
    {
        ret=now;
        top[block_nod].to=node[now].next;
        top[block_nod].siz--;
        top[block_nod].Map[node[now].cost]--;
    }
    else 
    {
        ret=node[now].next;
        node[now].next=node[node[now].next].next;
        top[block_nod].Map[node[ret].cost]--;
        top[block_nod].siz--;
    }
    if(top[block_nod].siz==0)
    {
        now=1;
        while(top[now].next!=block_nod) now=top[now].next;
        top[now].next=top[block_nod].next;
    }
    return ret;
}
void Insert(int wei,int nod)
{
    int now=1,sum=0;
    while(sum+top[now].siz<wei)
         sum+=top[now].siz,now=top[now].next;
    int block_nod=now,flag=0;now=top[now].to;
    while(wei-sum-flag>1) flag++,now=node[now].next;
    if(wei==0)
    {
        top[block_nod].to=nod;
        node[nod].next=now;
        top[block_nod].siz++;
        top[block_nod].Map[node[nod].cost]++;
    }
    else 
    {
        top[block_nod].siz++;
        top[block_nod].Map[node[nod].cost]++;
        node[nod].next=node[now].next;
        node[now].next=nod;
    }
    if(top[block_nod].siz>=k*2)
    {
        int now=top[block_nod].to;
        for(int i=1;i<k;i++)
            now=node[now].next;
        top[++tot].to=node[now].next;
        top[tot].siz=top[block_nod].siz-k;
        top[block_nod].siz=k;int zz=node[now].next;
        node[now].next=0;
        top[tot].next=top[block_nod].next;
        top[block_nod].next=tot;now=zz;
        while(now)
        {
            top[block_nod].Map[node[now].cost]--;
            top[tot].Map[node[now].cost]++;
            now=node[now].next;
        }
    }
}
int main()
{
    read(n),read(m);k=sqrt(n);
    for(int i=1;i<=n;i++) read(node[i].cost);
    for(int i=1;i<=n;i++) 
    {
        if(i%k==1) top[tot].to=i;
        top[tot].siz++;top[tot].Map[node[i].cost]++;
        if(i%k==0&&n!=i) tot++;
    }
    for(int i=1;i<=n;i++) node[i].next=(i%k!=0&&i!=n?i+1:0);
    for(int i=0;i<tot;i++) top[i].next=i+1;
    for(int cas=1;cas<=m;cas++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r);
        if(opt==1)
        {
            if(l==r) continue;
            c=Delete(r);
            Insert(l-1,c);
        }
        else
        {
            read(c);
            int now=1,sum=0,ans=0;
            while(sum+top[now].siz<l) 
                sum+=top[now].siz,now=top[now].next; 
            int L=now,sum_l=sum;
            while(sum+top[now].siz<r) sum+=top[now].siz,now=top[now].next; int R=now,sum_r=sum;
            if(L==R)
            {
                int siz=top[L].siz;
                now=top[now].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum+i>=l&&sum+i<=r) ans++;
                    now=node[now].next;
                }
            }
            else if(top[L].next==R)
            {
                int siz=top[L].siz;
                now=top[L].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_l+i>=l) ans++;
                    now=node[now].next;
                }
                siz=top[R].siz;
                now=top[R].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_r+i<=r) ans++;
                    now=node[now].next;
                }
            }
            else 
            {
                int siz=top[L].siz;
                now=top[L].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_l+i>=l) ans++;
                    now=node[now].next;
                }
                siz=top[R].siz;
                now=top[R].to;
                for(int i=1;i<=siz;i++)
                {
                    if(node[now].cost==c&&sum_r+i<=r) ans++;
                    now=node[now].next;
                }
                now=top[L].next;
                while(now!=R)
                {
                    ans+=top[now].Map[c];
                    now=top[now].next;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

提供一个对拍,可以用来测试正确性:屠龙宝刀,点击就送

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注