求助，如何卡常数
- 板块P4887 【模板】莫队二次离线（第十四分块(前体)）
- 楼主xiaolilsq
- 当前回复12
- 已保存回复12
- 发布时间2020/8/22 10:57
- 上次更新2023/11/6 19:41:30
查看原帖
被骇客银狼阻止的越权访问保存失败
求助，如何卡常数
如题，感觉自己的时间复杂度应该是对的，但是就是过不去，希望热心的谷民们可以教我如何卡过去，谢谢。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
int f;char c;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
static char q[64];int cnt=0;
if(!x)pc('0');if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=100005,maxm=100005;
struct Edgel{
int l,r,type,id,nt;
Edgel(int l=0,int r=0,int type=0,int id=0,int nt=0):
l(l),r(r),type(type),id(id),nt(nt){}
}el[maxm];
int hdl[maxn],numl;
void qwql(int u,int l,int r,int type,int id){
el[++numl]=Edgel(l,r,type,id,hdl[u]),hdl[u]=numl;
}
struct Edger{
int l,r,type,id,nt;
Edger(int l=0,int r=0,int type=0,int id=0,int nt=0):
l(l),r(r),type(type),id(id),nt(nt){}
}er[maxm];
int hdr[maxn],numr;
void qwqr(int u,int l,int r,int type,int id){
er[++numr]=Edger(l,r,type,id,hdr[u]),hdr[u]=numr;
}
int I[maxn];
struct Query{
int l,r,id;
Query(int l=0,int r=0,int id=0):
l(l),r(r),id(id){}
bool operator < (const Query o)const{
return I[l]^I[o.l]?l<o.l:I[l]&1?r<o.r:r>o.r;
}
}q[maxm];
int MT[16384],st[16384],tp,a[maxn];
long long pre[maxn],suf[maxn],Ans[maxm];
int main(){
int n,m,k;
read(n),read(m),read(k);
int sqr=sqrt(n);
for(int i=0;i<16384;++i){
int cnt=0,tmp=i;
while(tmp){
tmp^=tmp&(-tmp);
++cnt;
}
if(cnt==k)
st[tp++]=i;
}
for(int i=1;i<=n;++i)
read(a[i]),I[i]=I[i-1]+((i-1)%sqr==0);
for(int i=1;i<=n;++i){
pre[i]=MT[a[i]]+pre[i-1];
for(int j=0;j<tp;++j)
++MT[a[i]^st[j]];
}
memset(MT,0,sizeof MT);
for(int i=n;i>=1;--i){
suf[i]=MT[a[i]]+suf[i+1];
for(int j=0;j<tp;++j)
++MT[a[i]^st[j]];
}
memset(MT,0,sizeof MT);
for(int i=1;i<=m;++i){
int l,r;
read(l),read(r);
q[i]=Query(l,r,i);
}
sort(q+1,q+m+1);
for(int i=1,nl=1,nr=0;i<=m;++i){
int tl=q[i].l,tr=q[i].r;
if(nl>tl){Ans[q[i].id]+=suf[tl]-suf[nl];qwqr(nr+1,tl,nl-1,-1,q[i].id);nl=tl;}else
if(nl<tl){Ans[q[i].id]-=suf[nl]-suf[tl];qwqr(nr+1,nl,tl-1, 1,q[i].id);nl=tl;}
if(nr<tr){Ans[q[i].id]+=pre[tr]-pre[nr];qwql(nl-1,nr+1,tr,-1,q[i].id);nr=tr;}else
if(nr>tr){Ans[q[i].id]-=pre[nr]-pre[tr];qwql(nl-1,tr+1,nr, 1,q[i].id);nr=tr;}
}
for(int i=1;i<=n;++i){
for(int j=0;j<tp;++j)
++MT[a[i]^st[j]];
for(int j=hdl[i];j;j=el[j].nt){
int l=el[j].l,r=el[j].r,type=el[j].type,id=el[j].id;
for(int s=l;s<=r;++s)Ans[id]+=type*MT[a[s]];
}
}
memset(MT,0,sizeof MT);
for(int i=n;i>=1;--i){
for(int j=0;j<tp;++j)
++MT[a[i]^st[j]];
for(int j=hdr[i];j;j=er[j].nt){
int l=er[j].l,r=er[j].r,type=er[j].type,id=er[j].id;
for(int s=l;s<=r;++s)Ans[id]+=type*MT[a[s]];
}
}
memset(MT,0,sizeof MT);
for(int i=1;i<=m;++i)
Ans[q[i].id]+=Ans[q[i-1].id];
for(int i=1;i<=m;++i)
write(Ans[i]),pc('\n');
return 0;
}
/*
..]]]]/@@@@@@@@@@@@@@\]]]`.
,]]@@@@@@/[[`.. ..[[[@@@@@@@]].
,]@@@@[[. ]] ,]. ,[\@@@@]`
,/@@@[` ,` @@. ,@@@@@@@@@@@@` =@^ ,/\]` ,\@@@]`
]@@@[. ,\/ ,@\]]` ./@@@@@@@@^ ,[@@@//@ =@^ .@\ .. ,\@@\`
,/@@[. .]/@@@` ,@@@\=@@/@@[. @@OO]]OO@^ .@@@@.@/ /@. .]]=@.=@^ ,].,\@@].
,/@/` ]@@@/`]/@@@` =@^ =@^ ,O@@@@@@@` =@/@^\\@^ @@ @@[[@@@]`@@/ [@@\.
./@@` \@,@@@@^,]`@@. .@@@@..@@ ,[\@@/[[\@[[[` =@^,@@ ,@^,` .@\],\@@\][@@@. [@@]
,@@` .@@ /@@@/@@,@\ @@[ \@ .[[. ,[. ,[,/` =@@@^ .[\@@@@@[.\/ .\@\.
]@/` ./@] ,@\ ,@@@/`/@^ .,]]]]]]]]]`. ,@]@@,[@@@. \@@@@@@@@`,@@`
,@/..@@\@@/[@@` ,@@[`]/@@/` .]]@@@@@/ /@@ .@@@` =@@@@@]]` .. ,@@`=@] /@ ,@@`
,@@` ,/@@@\ ]@@` ,@@[` .. ,/@@@@@@/[[. .[... ...[. .\@@@@@@@@@. ,` ,].,@@`\@\=@. ,@\
/@` @@/ =@@/` ,/@@` . .,]` ]@@@@@ .@@@\]]` .. ,` ,@@\] ,@@/[/\@\,,@@. \@`
,@/ ,@@@@@`\@@` .[. ,]@@@@@@@@@^ /@@@@` [@@@@` =@@@@@@@O]]. .[\@] .\@\@@\@\,[. ,@\
,@^ .[. \/ ,]@@@` =@@@@@@@@@@/ /@@` .\@@. =@@@@@@@@@@\ =@\]. ,@@` .@@.
=@^ ]/@@@@@@@^ /@@@@@@@@@@@ =[ ,\ \@@@@@@@@@@\ ,@@@@@@\` . \@.
,@^ /@@@@@@@@@^ /@@@@[[[. .,[[\@@@\ =@@@@@@@@@\` @@
.@/ ,@@@@@@@@[[` .,]]]@@@@@[. .[@@@@@]]]. .[[\@@@@@@@\ .@\
/@. /@@/[. ,]/@.,@@@@@@@@[ ./@^ =@\. [@@@@@@@@`,@@\]` ,[@@` =@^
,@^ ,..]@@@@@@@@/ /@@@@@[ ]@@@@^ =@@@@] [@@@@@\ @@@@@@@@@\]. @@
=@. =@@@@@@@@@@@@^ @@@[ ]@@@@@@@^ =@@@@@@@] [@@@.=@@@@@@@@@@@@@. =@
@@ .@@@@@@@@@@@@@.=/. ,@@@@@@@@@@^ =@@@@@@@@@@` .\^=@@@@@@@@@@@@@^ ,@
@/ =@@@@@@@@@@@@/ ,/@@@@@@@@@@@@^ =@@@@@@@@@@@@@` .\@@@@@@@@@@@@@ .@
@\ ,\@@@@@@@@@@@@@^ =@@@@@@@@@@@@@@[. .. .@
@@ .@@@@@@@@@@@@@`. .[@@@@@@@@@@^ =@@@@@@@@@@/` .@@@@@@@@@@@@@^ ,@
=@. ,\@@@@@@@@@@^ @@\. ,\@@@@@@^ =@@@@@@@[. ,@@ =@@@@@@@@@@@[. =@
,@^ \\]. ,[\@@@@@ =@@@@\` .\@@@^ =@@@@` .]@@@@^ @@@@@@[` .]@. @@
\@. =@@@@@]]. .. \@@@@@@@` ,` =/. ,/@@@@@@/ .. .]]@@@@@@. =@^
.@\ ,@@@@@@@@@@@. ]]`. .,` ,[. .` @@@@@@@@@@@` .@/
=@^ ,\@@@@@@@@\ .@@@@@@@@@@@^ ,@@@@@@@@@@@ /@@@@@@@/` @@.
=@^ .[\@@@@\ .@@@@@@@@@@@` ,\` ,@^ @@@@@@@@@@@ /@@@/[. . /@.
=@^ ,. .[` \@@@@@@@@@@. =@@@` ]@@@/ /@@@@@@@@@/ .. .]//` @@.
,@\ ,\@\]` ,[[\@@@@` =@@@@@] ./@@@@@/ /@@/[[`. ,]@@@@[. ,@/
\@` [\@\ =@\]]]. .]]]/@@/. /@@[. /@^
,@\. . [@@@@@@@@\ ,@@@@ =@@@@` ,@@@@@@@@/ .. ,@/.
\@\ .,[[O@@@] ,@@@@@@@@@@@@@@/ ,@@@@@[[. ,]/@@@@@. ,@@`
\@\. ./@@@@@@@@@@@]. .... ,]]@@@@@@[` ,@@`
[@@` ,@@@@@@@@/[[[[@@@\/^ .]]]O@@O]]` ]. ,\@@@@@@@^ =@` ]@@`
,\@\. =@@@@@@@ ,@@ ./@@@@@@@/[[[@@@@ ,@@@@@@]/@@@@@^ ,@@/
,@@\` \@@@@@\ =@@@@@@@` .. \@@@@@/[. ,@@/`
,\@@] ,@@@@@@]. . @@@@@@@^ =@@@@@\ ./@@/.
.[@@@]. .[@@@@@@@@@@^ ,@@@@@@@\ ,/@^ ,@@@@@@@/ ,/@@@`
.[@@@\]. .. [@@@@@@@@@@@@@/[^ [[[`. ,]@@@/`
.[\@@@\]` .... .]]@@@@[`
.[[@@@@@@\]]`.. ..]]]@@@@@@/[`
*/
附：提交记录
加载中...