Loading...

洛谷P4135 作诗

check评论:0 条 remove_red_eye浏览量:736 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-23

经历了$5h$的惨无人道的调试,本蒟蒻终于$A$了

首先是预处理,我们一定要在$O(n\sqrt n)$内完成,我们只需要对于每个块开始向后扫一遍即可

我们用$f[i][j]$表示第$i$块到第$j$块的答案,$tot[i][j]$表示从第$i$块到序列末尾$j$出现的次数

因为$tot$具有可加减性,我们就不用分更细了

查询的时候,如果两端点所在块相邻或者相同就暴力,否则就先统计出中间的答案,再看两边多出来的,然后依次判断即可

不吸氧只有二十

code:

#include <bits/stdc++.h>
using namespace std;
int n,c,m,block,cnt[100010];
int belong[100010],f[500][500],a[100010];
int tot[500][100010];
void pre()
{
    for(int i=1;i<=belong[n];i++)
    {
        int maxans=0;
        for(int j=(i-1)*block+1;j<=n;j++)
        {
            tot[i][a[j]]++;
            if(tot[i][a[j]]&1&&tot[i][a[j]]>1)
            {
                maxans--;
            }
            else if(!(tot[i][a[j]]&1))
            {
                maxans++;
            }
            if(belong[j]!=belong[j+1]||j==n)
            {
                f[i][belong[j]]=maxans;
            } 
        }
    }
}
int tong[100010];
vector<int> vc;
int query(int l,int r)
{
    vc.clear();
    memset(tong,0,sizeof(tong));
    int ans=f[belong[l]+1][belong[r]-1];
    for(int i=l;i<=min(belong[l]*block,r);i++)
    {
        tong[a[i]]++;
        if(tong[a[i]]==1)
        {
            vc.push_back(a[i]);
        }
    }
    for(int i=(belong[r]-1)*block+1;i<=r;i++)
    {
           tong[a[i]]++;
        if(tong[a[i]]==1)
        {
            vc.push_back(a[i]);
        }
    }
    for(int i=0;i<vc.size();i++)
    {
        int k=tot[belong[l]+1][vc[i]]-tot[belong[r]][vc[i]];
           int m=k;
        k+=tong[vc[i]];
        tong[vc[i]]=0;
        if((k&1)&&(m%2==0)&&(m>1))
        {
            ans--;
        }
        if((k%2==0)&&((m&1)||m==0)&&(k>0))
        {
            ans++;
        }
    }
    return ans;
}
int main()
{
    cin>>n>>c>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        belong[i]=(i-1)/block+1;
    }
    pre();
    int las=0;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        l=(l+las)%n+1;
        r=(r+las)%n+1;
        if(l>r)
        {
            swap(l,r);
        }
        if(belong[l]==belong[r]||belong[l]+1==belong[r])
        {
            memset(tong,0,sizeof(tong));
            int ans=0;
            for(int j=l;j<=r;j++)
            {
                //cout<<a[j]<<endl;
                tong[a[j]]++;
                if(!(tong[a[j]]&1))
                {
                    ans++;
                }
                else if((tong[a[j]]&1)&&tong[a[j]]>1)
                {
                    ans--;
                }
            }
            printf("%d\n",ans);
            las=ans;
            continue;
        }
        las=query(l,r);
        printf("%d\n",las);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名