Loading...

洛谷P4137 Rmq Problem / mex

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

莫队题目

我们删除一个数很容易,取$min$就行,可是添加的话就略微麻烦

一种方法是我们每次加完重构一次$ans$,从$1$扫描到$n$,可以用值域分块优化一下,可是这样还是很慢,可以被卡死,第九个点不论怎样都过不去

考虑换一种思路

因为加上数之后答案至会变大,我们从当前答案网上找就可以了qwq

#include <bits/stdc++.h>
using namespace std;
int n,m,block;
int a[200010],anss[200010],tong[200010],ans;
struct query
{
    int id,l,r;
}q[200010];
bool cmp(query a,query b)
{
    return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}
int main()
{
    cin>>n>>m;
    block=n/sqrt((m<<1)/3);
    a[0]=-1; 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>n)
        {
            a[i]=-1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=0,r=0;
    ans=0;
    for(int i=1;i<=m;i++)
    {
        int flag=0;
        while(l<q[i].l)
        {
            int k=a[l];
            l++;
            if(k==-1)
            {
                continue;
            }
            tong[k]--;    
            if(tong[k]==0)
            {
                ans=min(ans,k);
            }
        }
        while(l>q[i].l)
        {
            l--;
            int k=a[l];
            if(k==-1)
            {
                continue;
            }    
            tong[k]++;
            int qaq=ans;
            while(tong[qaq]>0)
            {
                qaq++;
            }
            ans=qaq;
        }
        while(r>q[i].r)
        {
            int k=a[r];
            r--;
            if(k==-1)
            {
                continue;
            }
            tong[k]--;        
            if(tong[k]==0)
            {
                ans=min(ans,k);
            }
        }
        while(r<q[i].r)
        {
            r++;
            int k=a[r];
            if(k==-1)
            {
                continue;
            }    
            tong[k]++;
            int qaq=ans;
            while(tong[qaq]>0)
            {
                qaq++;
            }
            ans=qaq;
        }
        anss[q[i].id]=ans;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",anss[i]);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名