题目
思路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;
}