CSP板子集合
chinaxjh
2019-10-30 20:10:48
* 0 火车头（$CSP$中不要用，$OJ$上可以用来卡卡常）
```cpp
#pragma GCC target("sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx")
#pragma comment(linker,"/STACK:102400000,102400000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
```
* 1 线段树（区间改&区间求和）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
ll n,m,i,bo,x,y,z,a[N],ans[N*8],sum[N*8],xx[N*8],yy[N*8];
void build(int p,int l,int r)
{
xx[p]=l; yy[p]=r;
int mid;
if (l==r)
{
ans[p]=a[l];
return;
}
mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
ans[p]=ans[p*2]+ans[p*2+1];
}
void pushdown(int p)
{
if (!sum[p]) return;
ans[p*2]+=sum[p]*(yy[p*2]-xx[p*2]+1);
ans[p*2+1]+=sum[p]*(yy[p*2+1]-xx[p*2+1]+1);
sum[p*2]+=sum[p];
sum[p*2+1]+=sum[p];
sum[p]=0;
}
void jia(int p,int l,int r,ll z)
{
int mid;
if (l<=xx[p]&&yy[p]<=r)
{
ans[p]+=z*(yy[p]-xx[p]+1);
sum[p]+=z;
return;
}
pushdown(p);
mid=(xx[p]+yy[p])>>1;
if (l<=mid) jia(p*2,l,r,z);
if (mid<r) jia(p*2+1,l,r,z);
ans[p]=ans[p*2]+ans[p*2+1];
}
ll query(int p,int l,int r)
{
ll mid,anss;
anss=0;
if (l<=xx[p]&&yy[p]<=r) return ans[p];
pushdown(p);
mid=(xx[p]+yy[p])>>1;
if (l<=mid) anss+=query(p*2,l,r);
if (mid<r) anss+=query(p*2+1,l,r);
return anss;
}
int main()
{
scanf("%lld%lld",&n,&m);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);
for (i=1;i<=m;i++)
{
scanf("%lld",&bo);
if (bo==1)
{
scanf("%lld%lld%lld",&x,&y,&z);
jia(1,x,y,z);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(1,x,y));
}
}
}
```
* 2 树状数组（区间改&区间求和）
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000;
ll n,m,i,a1[N+5],a2[N+5],x,y,z,biao;
ll lowbit(ll x)
{
return x&(-x);
}
void add1(ll x,ll y)
{
ll i;
for (i=x;i<=n;i+=lowbit(i))
a1[i]+=y;
}
void add2(ll x,ll y)
{
ll i;
for (i=x;i<=n;i+=lowbit(i))
a2[i]+=y;
}
void jia(ll x,ll y,ll z)
{
add1(x,z);
add1(y+1,-z);
add2(x,z*x);
add2(y+1,-z*(y+1));
}
ll getsum1(ll x)
{
ll i,ans;
ans=0;
for (i=x;i>=1;i-=lowbit(i))
ans+=a1[i];
return ans;
}
ll getsum2(ll x)
{
ll i,ans;
ans=0;
for (i=x;i>=1;i-=lowbit(i))
ans+=a2[i];
return ans;
}
ll getans(ll l,ll r)
{
return r*getsum1(r)-getsum2(r)-(l*getsum1(l-1)-getsum2(l-1));
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%lld",&x);
jia(i,i,x);
}
for (i=1;i<=m;i++)
{
scanf("%d",&biao);
if (biao==1)
{
scanf("%lld%lld%lld",&x,&y,&z);
jia(x,y,z);
}
else
{
scanf("%lld%lld",&x,&y);
y++;
printf("%lld\n",getans(x,y));
}
}
}
```
* 3 康拓展开
```pascal
const Max_n=1000002; mo=998244353;
var
a,tree,getmin:array[1..Max_n+50] of longint;
jie:array[0..Max_n+50] of int64;
n,i:longint;
function lowbit(x:longint):longint;
begin
exit(x and (-x));
end;
function sum(x:longint):longint;
var
i,ans:longint;
begin
i:=x; ans:=0;
while i>0 do
begin
ans:=ans+tree[i];
i:=i-lowbit(i);
end;
exit(ans);
end;
procedure ru(x:longint);
var
i:longint;
begin
i:=x;
while i<=Max_n do
begin
inc(tree[i]);
i:=i+lowbit(i);
end;
end;
procedure yu;
var
i:longint;
begin
jie[0]:=1;
for i:=1 to Max_n do
jie[i]:=(jie[i-1]*i) mod mo;
end;
procedure contor;
var
anss:int64;
i:longint;
begin
anss:=0;
for i:=n downto 1 do
begin
getmin[i]:=sum(a[i]-1);
ru(a[i]);
end;
for i:=1 to n do
anss:=(anss+jie[n-i]*getmin[i]) mod mo;
writeln((anss+1) mod mo);
end;
begin
yu;
readln(n);
for i:=1 to n do read(a[i]);
contor;
end.
```
* 4 线性筛素数
```
var
a:array[1..10000000] of boolean;
i,j,n,m:longint;
begin
read(n,m);
a[1]:=true;
for i:=2 to trunc(sqrt(n)) do
begin
if not a[i] then
begin
for j:=2 to n div i do
a[i*j]:=true;
end;
end;
for i:=1 to m do
begin
read(n);
if not a[n] then writeln('Yes')
else writeln('No');
end;
end.
```
* 5 链式前向星
```cpp
void add(int x,int y)
{
len++;
to[len]=y;
nxt[len]=las[x];
las[x]=len;
}
```