缺了氧气你不行。
by 清风我已逝 @ 2018-10-25 20:09:15
@[g21glf](/space/show?uid=31639) 求助大佬，为什么我分块吸氧才80
by 7KByte @ 2019-03-09 22:27:51
@[Gang_Leader](/space/show?uid=119261) emmm，你咋写的？
by Thosaka_Forest @ 2019-03-10 08:52:58
@[Gang_Leader](/space/show?uid=119261)
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,k,tot;
int id[MAXN],l[MAXN],r[MAXN];
int a[MAXN],b[MAXN];
inline int Read()
{
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
inline void fenkuai()
{
for(int i=1;i<=tot;i++)
l[i]=(i-1)*tot+1,r[i]=i*tot;
for(int i=1;i<=n;i++)
id[i]=(i-1)/tot+1;
if(r[tot]<n)
{
tot++;
r[tot]=n;
l[tot]=r[tot-1]+1;
for(int i=l[tot];i<=r[tot];i++)
id[i]=tot;
}
for(int i=1;i<=tot;i++)
sort(a+l[i],a+r[i]+1);
}
inline void change(int x,int y)
{
b[x]=y;
for(int i=l[id[x]];i<=r[id[x]];i++)
a[i]=b[i];
sort(a+l[id[x]],a+r[id[x]]+1);
}
inline int query(int x,int y,int key)
{
int ret=0;
if(id[x]==id[y])
{
for(int i=x;i<=y;i++)
if(b[i]==key)
ret++;
return ret;
}
for(int i=id[x]+1;i<=id[y]-1;i++)
{
int minn=lower_bound(a+l[i],a+r[i]+1,key)-a;
int maxx=lower_bound(a+l[i],a+r[i]+1,key+1)-a-1;
ret+=maxx-minn+1;
}
for(int i=x;i<=r[id[x]];i++)
if(b[i]==key)
ret++;
for(int i=l[id[y]];i<=y;i++)
if(b[i]==key)
ret++;
return ret;
}
int main()
{
n=Read();m=Read();
for(int i=1;i<=n;i++)
a[i]=b[i]=Read();
tot=sqrt(n);
fenkuai();
while(m--)
{
char opt[5];
scanf("%s",opt);
if(opt[0]=='C')
{
int x=Read(),y=Read();
change(x,y);
}
else
{
int x=Read(),y=Read(),key=Read();
cout<<query(x,y,key)<<'\n';
}
}
return 0;
}
```
我的代码
by Thosaka_Forest @ 2019-03-10 08:53:16
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int L[1005],R[1005],pos[100005],a[100005];
map<int,int>M[1005];
inline int read(){
int a=0;char x=getchar();
while(x<'0'||x>'9') x=getchar();
while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar();
return a;
}
int ask(int l,int r,int data){
int x=pos[l],y=pos[r];
int ans=0;
if(x==y){
for(int i=l;i<=r;i++)
ans+=(a[i]==data);
return ans;
}
for(int i=x+1;i<y;i++)
ans+=M[i][data];
for(int i=l;i<=R[x];i++)
ans+=a[i]==data;
for(int i=L[y];i<=r;i++)
ans+=a[i]==data;
return ans;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
t=sqrt(n);
for(int i=1;i<=t;i++)
L[i]=(i-1)*t+1,
R[i]=i*t;
if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
for(int i=1;i<=t;i++)
for(int j=L[i];j<=R[i];j++)
pos[j]=i,M[i][a[j]]++;
char k[3];int x,y,z;
for(int i=1;i<=m;i++){
scanf("%s",k);
if(k[0]=='C'){
x=read();y=read();
M[pos[x]][a[x]]--;
M[pos[x]][y]++;
a[x]=y;
}
else{
x=read();y=read();z=read();
printf("%d\n",ask(x,y,z));
}
}
return 0;
}
```
by 7KByte @ 2019-03-10 09:19:56
$O(M\sqrt NlogN)$本来就会T吧..保存每一块各个数字出现次数再加和能去掉log
by cbio @ 2020-01-08 18:58:10
@[Thosaka_Forest](/user/31639)
by cbio @ 2020-01-08 18:58:27
嗯我吸氧也80
by ACPC @ 2023-01-11 08:52:29