P3939 数颜色

题目

P3939 数颜色

思路1(待修莫队)

哇，这不是莫队模板题吗
3e5，TLE45分
不行 我有信仰啊
pow(n,0.66666)
75分

思路2(vector+二分)

怕不是数据结构学傻了
开vector直接桶拍二分呀

代码1

#include <cmath>
#include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=3e5+7;
inline int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
inline void print(int x) {
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
int n,m,A,B,belong[maxn],a[maxn],vis[maxn],C[maxn];
struct query {
    int l,r,tim,id,ans,k;
}Q[maxn];
inline bool cmp1(const query &a,const query &b) {
    return belong[a.l]^belong[b.l] ? a.l<b.l : belong[a.r]^belong[b.r] ? belong[a.l]&1 ? a.r<b.r :a.r>b.r : belong[a.r]&1  ? a.tim<b.tim : a.tim>b.tim;
}
inline bool cmp2(const query &a,const query &b) {
    return a.id<b.id;
}
inline void work(int i,int x,int y) {
    if(Q[i].l<=x&&x<=Q[i].r)
        --vis[a[x]],++vis[a[y]];
    if(Q[i].l<=y&&y<=Q[i].r)
        ++vis[a[x]],--vis[a[y]];
    swap(a[x],a[y]);
}
int main() {    
    n=read(),m=read();
    int k=2100;
    FOR(i,1,n) a[i]=read();
    FOR(i,1,n) belong[i]=(i-1)/k+1;
    FOR(i,1,m) {
        int opt=read();
        if(opt==1)
            Q[++A].id=A,Q[A].l=read(),Q[A].r=read(),Q[A].k=read(),Q[A].tim=B;
        else
            C[++B]=read();
    }
    sort(Q+1,Q+1+A,cmp1);
    int l=1,r=0,t=0;
    FOR(i,1,A) {
        for(;l > Q[i].l;) ++vis[a[--l]];
        for(;r < Q[i].r;) ++vis[a[++r]];
        for(;l < Q[i].l;) --vis[a[l++]];
        for(;r > Q[i].r;) --vis[a[r--]];

        for(;t > Q[i].tim;) work(i,C[t],C[t]+1),--t;
        for(;t < Q[i].tim;) ++t,work(i,C[t],C[t]+1);
  
        Q[i].ans=vis[Q[i].k];
    }
    sort(Q+1,Q+1+A,cmp2);
    FOR(i,1,A) print(Q[i].ans),puts("");
    return 0;
}

代码2

#include <iostream>
#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define pb(x) push_back(x)
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=3e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,m,b[maxn];
vector<int> a[maxn];
int main() {
    n=read(),m=read();
    FOR(i,1,n) b[i]=read();
    FOR(i,1,n) a[1].pb(-0x3f3f3f3f);
    FOR(i,1,n) a[b[i]].pb(i);
    FOR(i,1,m) {
        int opt=read();
        if(opt==1) {
            int l=read(),r=read(),x=read();
            int ans=upper_bound(a[x].begin(),a[x].end(),r)-a[x].begin();
            ans-=upper_bound(a[x].begin(),a[x].end(),l-1)-a[x].begin();
            cout<<ans<<"\n";
        } else {           
            int x=read();
            if(b[x]==b[x+1]) continue;
            int j;
            j=lower_bound(a[b[x]].begin(),a[b[x]].end(),x)-a[b[x]].begin();
            a[b[x]][j]=x+1;
            j=lower_bound(a[b[x+1]].begin(),a[b[x+1]].end(),x+1)-a[b[x+1]].begin();
            a[b[x+1]][j]=x;
            swap(b[x],b[x+1]);
        }
    }
    return 0;
}