来欣赏一下T3赛时打的9K代码
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
namespace inout
{
#define super faster
#ifdef super
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
template<typename tn> il void read(tn &x)
{
x=0;
register bool op=false;
register char ch=getchar();
while(ch<'0'||ch>'9')
{
op|=(ch=='-');
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
if(op)
{
x=(~x)+1;
}
}
template<typename tn> void writen(tn x)
{
if(x)
{
writen(x/10);
putchar((x%10)|'0');
}
}
template<typename tn> il void write(tn x,char y=' ')
{
if(x<0)
{
putchar('-'),x=(~x)+1;
}
if(!x)
{
putchar('0');
}
writen(x),putchar(y);
}
}using namespace inout;
int a,c,in[200002];
long long b[200002],u[200002],v[200002],w[200002];
bool te,one,two,thr,fou,fiv;
namespace task0
{
int wd[200002];
bool lf[200002];
short main()
{
memset(lf,true,sizeof(lf));
for(ri i=1;i<=c;i++)
{
// cout<<i<<'\n';
switch(in[i])
{
case 1:
{
for(ri j=u[i];j<=v[i];j++)
{
if(lf[j])
{
if(wd[j])
{
wd[j]--;
}
else
{
b[j]-=w[i];
if(b[j]<0)
{
lf[j]=false;
}
}
}
}
break;
}
case 2:
{
for(ri j=u[i];j<=v[i];j++)
{
if(lf[j])
{
b[j]+=w[i];
}
}
break;
}
case 3:
{
if(lf[u[i]])
{
wd[u[i]]++;
}
break;
}
case 4:
{
ri rn=0;
for(ri j=u[i];j<=v[i];j++)
{
if(!lf[j])
{
rn++;
}
}
write(rn,'\n');
break;
}
case 5:
{
ri rn=0;
for(ri j=u[i];j<=v[i];j++)
{
if(lf[j]&&!b[j])
{
rn++;
}
}
write(rn,'\n');
break;
}
}
}
return 0;
}
}
namespace task1
{
int wd[200002];
bool lf[200002];
short main()
{
memset(lf,true,sizeof(lf));
for(ri i=1;i<=c;i++)
{
switch(in[i])
{
case 1:
{
if(lf[u[i]])
{
if(wd[u[i]])
{
wd[u[i]]--;
}
else
{
b[u[i]]-=w[i];
if(b[u[i]]<0)
{
lf[u[i]]=false;
}
}
}
break;
}
case 2:
{
if(lf[u[i]])
{
b[u[i]]+=w[i];
}
break;
}
case 3:
{
if(lf[u[i]])
{
wd[u[i]]++;
}
break;
}
case 4:
{
if(lf[u[i]])
{
write(0,'\n');
}
else
{
write(1,'\n');
}
break;
}
case 5:
{
if(lf[u[i]])
{
if(!b[u[i]])
{
write(1,'\n');
}
else
{
write(0,'\n');
}
}
else
{
write(0,'\n');
}
break;
}
}
}
return 0;
}
}
namespace task2
{
int be[200002],lt[505],rt[505],cnt,len;
long long del[505],d[200002];
il void pre()
{
len=sqrt((double)a*1.0*log2(a));
cnt=a/len;
for(ri i=1;i<=cnt;i++)
{
lt[i]=rt[i-1]+1;
rt[i]=rt[i-1]+len;
}
if(rt[cnt]!=a)
{
cnt++;
lt[cnt]=rt[cnt-1]+1;
rt[cnt]=a;
}
for(ri i=1;i<=cnt;i++)
{
for(ri j=lt[i];j<=rt[i];j++)
{
be[j]=i;
d[j]=b[j];
}
sort(d+lt[i],d+rt[i]+1);
}
}
il void add(int l,int r,int x)
{
if(be[l]==be[r])
{
ri h=be[l];
for(ri i=l;i<=r;i++)
{
b[i]-=x;
}
for(ri i=lt[h];i<=rt[h];i++)
{
d[i]=b[i];
}
sort(d+lt[h],d+rt[h]+1);
}
else
{
ri h=be[l];
for(ri i=l;i<=rt[h];i++)
{
b[i]-=x;
}
for(ri i=lt[h];i<=rt[h];i++)
{
d[i]=b[i];
}
sort(d+lt[h],d+rt[h]+1);
for(ri i=be[l]+1;i<=be[r]-1;i++)
{
del[i]+=x;
}
h=be[r];
for(ri i=lt[h];i<=r;i++)
{
b[i]-=x;
}
for(ri i=lt[h];i<=rt[h];i++)
{
d[i]=b[i];
}
sort(d+lt[h],d+rt[h]+1);
}
}
il int find1(int l,int r)
{
ri rn=0;
if(be[l]==be[r])
{
ri h=be[l];
for(ri i=l;i<=r;i++)
{
if(b[i]-del[h]<0)
{
rn++;
}
}
}
else
{
ri h=be[l];
for(ri i=l;i<=rt[h];i++)
{
if(b[i]-del[h]<0)
{
rn++;
}
}
for(ri i=be[l]+1;i<=be[r]-1;i++)
{
rn+=upper_bound(d+lt[i],d+rt[i]+1,del[i]-1)-d-lt[i];
}
h=be[r];
for(ri i=lt[h];i<=r;i++)
{
if(b[i]-del[h]<0)
{
rn++;
}
}
}
return rn;
}
il int find2(int l,int r)
{
ri rn=0;
if(be[l]==be[r])
{
ri h=be[l];
for(ri i=l;i<=r;i++)
{
if(b[i]==del[h])
{
rn++;
}
}
}
else
{
ri h=be[l];
for(ri i=l;i<=rt[h];i++)
{
if(b[i]==del[h])
{
rn++;
}
}
for(ri i=be[l]+1;i<=be[r]-1;i++)
{
rn+=upper_bound(d+lt[i],d+rt[i]+1,del[i])-lower_bound(d+lt[i],d+rt[i]+1,del[i]);
}
h=be[r];
for(ri i=lt[h];i<=r;i++)
{
if(b[i]==del[h])
{
rn++;
}
}
}
return rn;
}
short main()
{
for(ri i=1;i<=c;i++)
{
switch(in[i])
{
case 1:
{
add(u[i],v[i],w[i]);
break;
}
case 4:
{
write(find1(u[i],v[i]),'\n');
break;
}
case 5:
{
write(find2(u[i],v[i]),'\n');
break;
}
}
}
return 0;
}
}
namespace task3
{
struct node
{
int left,right,min,sum,lazy;
}str[800008];
il int ls(int x)
{
return x<<1;
}
il int rs(int x)
{
return x<<1|1;
}
il void pu(int x)
{
if(str[ls(x)].min<str[rs(x)].min)
{
str[x].min=str[ls(x)].min;
str[x].sum=str[ls(x)].sum;
return;
}
if(str[ls(x)].min>str[rs(x)].min)
{
str[x].min=str[rs(x)].min;
str[x].sum=str[rs(x)].sum;
return;
}
str[x].min=str[ls(x)].min;
str[x].sum=str[ls(x)].sum+str[rs(x)].sum;
}
il void pd(int x)
{
if(str[x].lazy)
{
ri lz=str[x].lazy;
str[x].lazy=0;
str[ls(x)].lazy+=lz;
str[ls(x)].min+=lz;
str[rs(x)].lazy+=lz;
str[rs(x)].min+=lz;
}
}
void makstr(int x,int lt,int rt)
{
str[x].left=lt;
str[x].right=rt;
if(lt==rt)
{
str[x].min=b[lt];
str[x].sum=1;
return;
}
ri me=(lt+rt)>>1;
makstr(ls(x),lt,me);
makstr(rs(x),me+1,rt);
pu(x);
}
void adstr(int x,int lt,int rt,int y)
{
if(lt<=str[x].left&&str[x].right<=rt)
{
str[x].lazy+=y;
str[x].min+=y;
return;
}
pd(x);
ri me=(str[x].left+str[x].right)>>1;
if(lt<=me)
{
adstr(ls(x),lt,rt,y);
}
if(rt>me)
{
adstr(rs(x),lt,rt,y);
}
pu(x);
}
pair<int,int> foudstr(int x,int lt,int rt)
{
if(lt<=str[x].left&&str[x].right<=rt)
{
return {str[x].min,str[x].sum};
}
pd(x);
ri me=(str[x].left+str[x].right)>>1;
register pair<int,int> rn1={-1,-1},rn2={-1,-1};
if(lt<=me)
{
rn1=foudstr(ls(x),lt,rt);
}
if(rt>me)
{
rn2=foudstr(rs(x),lt,rt);
}
if(rn1.second>=0&&rn2.second>=0)
{
if(rn1.first<rn2.first)
{
return rn1;
}
if(rn1.first>rn2.first)
{
return rn2;
}
return {rn1.first,rn1.second+rn2.second};
}
else
{
if(rn1.second>=0)
{
return rn1;
}
else
{
return rn2;
}
}
}
short main()
{
makstr(1,1,a);
for(ri i=1;i<=c;i++)
{
switch(in[i])
{
case 1:
{
adstr(1,u[i],v[i],-w[i]);
break;
}
case 2:
{
adstr(1,u[i],v[i],w[i]);
break;
}
case 5:
{
register pair<int,int> rn=foudstr(1,u[i],v[i]);
if(rn.first!=0)
{
rn.second=0;
}
write(rn.second,'\n');
break;
}
}
}
return 0;
}
}
int main()
{
// freopen("C.in","r",stdin);
// freopen("ex_simulator2.in","r",stdin);
// freopen("myex_simulator2.out","w",stdout);
freopen("simulator.in","r",stdin);
freopen("simulator.out","w",stdout);
te=true;
read(a);
for(ri i=1;i<=a;i++)
{
read(b[i]);
}
read(c);
for(ri i=1;i<=c;i++)
{
read(in[i]);
switch(in[i])
{
case 1:
{
read(u[i]),read(v[i]),read(w[i]);
if(u[i]!=v[i])
{
te=false;
}
one=true;
break;
}
case 2:
{
read(u[i]),read(v[i]),read(w[i]);
if(u[i]!=v[i])
{
te=false;
}
two=true;
break;
}
case 3:
{
read(u[i]);
thr=true;
break;
}
case 4:
{
read(u[i]),read(v[i]);
if(u[i]!=v[i])
{
te=false;
}
fou=true;
break;
}
case 5:
{
read(u[i]),read(v[i]);
if(u[i]!=v[i])
{
te=false;
}
fiv=true;
break;
}
}
}
// exit(0);
if(te)
{
return task1::main();
}
if(!two&&!thr)
{
return task2::main();
}
if(!thr&&!fou)
{
return task3::main();
}
return task0::main();
return 0;
}
/*
10
10 10 10 10 10 10 10 10 10 10
20
4 1 10
5 3 6
1 1 1 10
5 1 3
4 1 5
1 1 2 20
4 2 5
4 1 6
1 1 8 10
5 1 10
4 1 10
1 9 9 1
1 9 9 1
1 8 8 2
4 1 4
5 3 6
1 7 10 2
5 1 10
4 1 10
4 5 8
*/
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！
为什么要卡我 \(O(n\sqrt{n\log n})\) 分块？！