有人帮忙看下这个 hack 有锅么 /bx
by E1_de5truct0r @ 2022-11-22 15:21:46
第一篇题解的数组开小了。
by 苏联小渣 @ 2022-11-22 15:26:23
第 16 篇是不是加了反作弊啊,CE 了。
第 17 篇 RE 了。
第 18 篇 RE 了。
第 19 篇 TLE 了。
第 20 篇 RE 了。
by E1_de5truct0r @ 2022-11-22 15:28:28
5、7 篇题解都是数组开小了,估计是原题加强过数据。
by 苏联小渣 @ 2022-11-22 15:28:53
RE 的大概都是这个问题。
by 苏联小渣 @ 2022-11-22 15:29:18
@[苏联小渣](/user/399286) 好像是,我看后面有的题解只开了 50000
by E1_de5truct0r @ 2022-11-22 15:29:25
第 21 个也 RE 了;
第 22 个 TLE 了;
第 23 个 RE 了;
第 24 个 RE 了;
第 25 个 RE 了;
第 26 个 RE 了;
第 27 个 RE 了。
by E1_de5truct0r @ 2022-11-22 15:32:02
好像是原题数据经过加强,但是还是请求管理撤下不能通过的题解,然后 RE 的题解可以改一下数组大小。
by E1_de5truct0r @ 2022-11-22 15:32:50
@[_RSY_](/user/46197)
by E1_de5truct0r @ 2022-11-22 15:33:00
上面那个数据是我拿第二个题解造的。
然后借楼求调我的分块(
```cpp
#include <bits/stdc++.h>
#define _cst const
#define _IfD long long
#define _siz 20
char buf[1<<_siz],buffer[1<<_siz],*p1=buf,*p2=buf,c=' ';
int op1=-1; _cst int op2=(1<<_siz)-1;
inline char gc(){return (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<_siz,stdin)),p1==p2?EOF:*p1++);}
inline void flush(){fwrite(buffer,1,op1+1,stdout),op1=-1;}
inline void pc(_cst char &x){if(op1==op2)flush();buffer[++op1]=x;}
template<typename T>void read(T &w){
w=0;bool f=1;char ch=gc();
for(;ch<=32;ch=gc()); if(ch=='-')f=0;
for(;'0'<=ch && ch<='9';ch=gc()) w=(w<<1)+(w<<3)+(ch^48);
w=f?w:-w;
}template<typename T,typename ...Arg>void read(T &w,Arg &...arg){
read(w); read(arg...);
}template<typename T>void wrt(T x){
if(x<0) pc('-'),x=-x;
if(x>9) wrt(x/10);
pc(x%10|48);
}template<typename T>void write(T x){
wrt(x); pc(c);
}template<typename T,typename ...Arg>void write(T x,Arg ...arg){
write(x); write(arg...);
}inline _IfD pow_10(_IfD x){
_IfD base=10,ans=1;
while(x) ans*=((x&1)?base:1),base*=base,x>>=1;
return ans;
}template<typename T>void readd(T &w){
w=0; _IfD x=0,cnt=0; bool f=1; char ch=gc();
for(;ch<=32;ch=gc()); if(ch=='-')f=0;
for(;'0'<=ch && ch<='9';ch=gc()) x=(x<<1)+(x<<3)+(ch^48);
w=(T)(f?x:-x);
if(ch!='.') return; x=0,ch=gc();
for(;'0'<=ch && ch<='9';ch=gc(),++cnt) x=(x<<1)+(x<<3)+(ch^48);
T tmp=(T)(x/(T)pow_10(cnt));
w=w+(T)(f?tmp:-tmp);
}template<typename T,typename ...Arg>void readd(T &w,Arg &...arg){
readd(w); readd(arg...);
}
template<typename T>inline T qmax(_cst T &a,_cst T &b){return a>b?a:b;}
template<typename T,typename ...Arg>inline T qmax(_cst T &a,_cst T &b,_cst Arg &...arg){return qmax(a,qmax(b,arg...));}
template<typename T>inline T qmin(_cst T &a,_cst T &b){return a<b?a:b;}
template<typename T,typename ...Arg>inline T qmin(_cst T &a,_cst T &b,_cst Arg &...arg){return qmin(a,qmin(b,arg...));}
template<typename T>inline void qswap(T &a,T &b){a+=b,b=a-b,a-=b;}
// 以上为缺省源
using namespace std;
const int MAXN=300005,MAXM=1205;
int all[MAXN],cnt,len;
int a[MAXN],bel[MAXN],f[MAXM][MAXM],g[MAXM][MAXN];
char op[MAXN]; int x[MAXN],y[MAXN];
int h[MAXN];
inline int get(int x,int y,int z){
if(x>y) return 0;
return g[y][z]-g[x-1][z];
}
int main(){
// freopen("i1.txt","r",stdin);
// freopen("ia.out","w",stdout);
int n,m; read(n,m);
for(int i=1;i<=n;i++) read(a[i]),all[++cnt]=a[i];
for(int i=1;i<=m;i++){
op[i]=gc(); read(x[i],y[i]);
if(op[i]=='R') all[++cnt]=y[i];
}
sort(all+1,all+1+cnt);
cnt=unique(all+1,all+1+cnt)-all-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(all+1,all+1+cnt,a[i])-all;
for(int i=1;i<=m;i++) if(op[i]=='R') y[i]=lower_bound(all+1,all+1+cnt,y[i])-all;
len=(int)(pow(n,0.55));
// cout<<len<<'\n';
int tot=0;
for(int i=1;i<=n;i++){
if(i%len==1) tot++;
bel[i]=tot;
}
for(int i=1;i<=tot;i++){
for(int j=1;j<=cnt;j++) h[j]=0;
for(int j=1;j<=cnt;j++) g[i][j]=g[i-1][j];
for(int j=(i-1)*len+1;j<=qmin(n,i*len);j++) g[i][a[j]]++;
for(int j=i;j<=tot;j++){
f[i][j]=f[i][j-1];
for(int k=(j-1)*len+1;k<=qmin(n,j*len);k++){
if(!h[a[k]]) f[i][j]++;
h[a[k]]++;
}
}
}
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++){
// cout<<"i: "<<i<<'\n';
if(op[i]=='R'){
if(a[x[i]]==y[i]) continue;
for(int j=bel[x[i]];j<=tot;j++) g[j][a[x[i]]]--;
for(int j=bel[x[i]];j<=tot;j++) g[j][y[i]]++;
for(int j=1;j<=bel[x[i]];j++){
for(int k=bel[x[i]];k<=tot;k++){
if(g[k][a[x[i]]]-g[j-1][a[x[i]]]==0) f[j][k]--;
if(g[k][y[i]]-g[j-1][y[i]]==1) f[j][k]++;
}
}
a[x[i]]=y[i];
}else{
vector<int> vec;
int ans=f[bel[x[i]]+1][bel[y[i]]-1];
for(int j=x[i];bel[j]==bel[x[i]] && j<=y[i];j++){
if(!h[a[j]] && !get(bel[x[i]]+1,bel[y[i]]-1,a[j])) ans++;
h[a[j]]=1,vec.push_back(a[j]);
}
for(int j=y[i];bel[j]==bel[y[i]] && j>=x[i];j--){
if(!h[a[j]] && !get(bel[x[i]]+1,bel[y[i]]-1,a[j])) ans++;
h[a[j]]=1,vec.push_back(a[j]);
}
for(int i:vec) h[i]=0;
wrt(ans),pc(10);
}
}
return flush(),0;
}
```
by E1_de5truct0r @ 2022-11-22 15:34:48