整除分块
(O(sqrt n)) 复杂度快速计算 (sumlimits_{i=1}^n lfloor n/i floor)
分块：(forall iin [l,r],lfloor n/i floor=C)
枚举 (l=1cdots n)推导 (r) 的过程：
(lfloor n/l floor=lfloor n/r floor=C)
(lCle n,rCle n,(r+1)C>n)
(rin (lfloor n/C floor-1,lfloor n/C floor])
( herefore r=lfloor n/C floor=lfloor n/lfloor n/l floor floor)
结论：(forall iin [l,lfloor n/lfloor n/l floor floor],lfloor n/i floor=mathrm{constant})
模板：[CQOI2007]余数求和
#include<bits/stdc++.h>
using namespace std;
#define int long long
int s(int l,int r){
return (l+r)*(r-l+1)/2;
}
int j(int n,int k){
int ans=n*k;
for(int l=1,r=1;l<=n;l=r+1){
r=k/l?min(k/(k/l),n):n;
ans-=s(l,r)*(k/l);
}
return ans;
}
signed main(){
int n,k; scanf("%lld%lld",&n,&k);
printf("%lld",j(n,k));
return 0;
}
注意事项：计算除法时要注意除数不能为零
差分约束
(O(nm)) 复杂度解 (x_i-x_jle Delta) 的不等式组问题
考虑 Bellman_Ford 算法中的松弛操作中的三角形不等式：(dis_ule dis_v+w)
将原不等式组全部变形为 (x_ile x_j+Delta)，可以直观地发现两者非常类似。
由此，我们将 (x_i) 看作图中的结点，对于每一个约束条件 (x_ile x_j+Delta)，连一条 ((j,i,Delta)) 的有向边。为什么是有向边？
显然，(x_j+Delta) 只能说明 (j) 到 (i) 有一条权值为 (Delta) 的边，反之则不能。
特别地，有时在添加所有约束条件后整个图仍未联通。不失一般性，为防止这种情况出现，需要添加一个虚点，并将这个虚点与其他的所有点连一条权值为零的有向边。
通过这一过程，我们便将原来的代数问题转化为图论的最短路问题，即可在 (O(nm)) 的时间复杂度内解决此问题。
需要注意，可能会出现无解的情况，在图论的意义上即是产生负环。
模板：
LuoguP3385 【模板】负环
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int maxm=3005;
const int INF=0x3f3f3f3f;
struct Edge{
int frm;
int to;
int nxt;
int val;
}edge[maxm<<1];
int tot,hd[maxn],dis[maxn];
int n,m;
void adde(int u,int v,int w){
edge[++tot].frm=u;
edge[tot].to=v;
edge[tot].nxt=hd[u];
edge[tot].val=w;
hd[u]=tot;
}
bool bellman_ford(){
for(int i=1;i<=n;i++)
for(int j=1;j<=tot;j++){
if(dis[edge[j].frm]!=INF&&dis[edge[j].frm]+edge[j].val<dis[edge[j].to]){
if(i==n)return true;
dis[edge[j].to]=dis[edge[j].frm]+edge[j].val;
}
}
return false;
}
int main(){
int T; scanf("%d",&T);
while(T--){
tot=0;
memset(hd,0,sizeof hd);
memset(dis,INF,sizeof dis);
dis[1]=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
adde(u,v,w);
if(w>=0)adde(v,u,w);
}
bool ok=bellman_ford();
printf("%s
",ok?"YES":"NO");
}
return 0;
}
LuoguP1993 小 K 的农场
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
template<typename S,typename T>bool up(S&a,T b){return (a<b)?(a=b,1):0;}
template<typename S,typename T>bool down(S&a,T b){return (a>b)?(a=b,1):0;}
const int maxn=5e3+5;
int S,n,m,dis[maxn],cnt[maxn];
bool inq[maxn];
struct Edge{
int to;
int nxt;
int val;
}edge[maxn<<1];
int tot,hd[maxn];
void adde(int u,int v,int w){
edge[++tot].to=v;
edge[tot].nxt=hd[u];
edge[tot].val=w;
hd[u]=tot;
}
bool SPFA(){
queue<int> q;
q.push(S);
memset(dis,0x3f,sizeof dis);
dis[S]=0;
inq[S]=true; cnt[S]=0;
while(q.size()){
int u=q.front(); q.pop();
inq[u]=false;
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val){
dis[v]=dis[u]+edge[i].val;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n) return false;
if(!inq[v]) inq[v]=true,q.push(v);
}
}
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int op,a,b,c;
scanf("%d%d%d",&op,&a,&b);
if(op==1) scanf("%d",&c),adde(a,b,-c);
else if(op==2) scanf("%d",&c),adde(b,a,c);
else adde(b,a,0);
}
S=n+1;
rep(i,1,n) adde(S,i,0);
printf("%s",SPFA()?"Yes":"No");
return 0;
}
01Trie
模板：AcWing143 最大异或对
将每个数的二进制表示从高位到低位依次插入 01 Trie，使得高位的数深度小。
在线查找之前的与当前数异或值最大的数。具体地从 Trie 深度小的地方开始找当前位异或值为 1 的数，逐渐向深度大的地方查找。
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int maxn=1<<17;
struct Trie{
int tr[maxn*30][2],tot;
void ins(int x){
int p=0;
for(int i=30;i>=0;i--){
int t=x>>i&1;
if(!tr[p][t]) tr[p][t]=++tot;
p=tr[p][t];
}
}
int qry(int x){
int p=0,res=0;
for(int i=30;i>=0;i--){
int t=x>>i&1; res<<=1;
if(tr[p][t^1]) res|=1,p=tr[p][t^1];
else p=tr[p][t];
}
return res;
}
}trie;
int main(){
int n;
scanf("%d",&n);
int ans=0;
rep(i,1,n){
int x; scanf("%d",&x);
trie.ins(x); ans=max(ans,trie.qry(x));
}
printf("%d",ans);
return 0;
}
扩展到树上同理。
AcWing144 最大异或值路径
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
void rd(int&x){
x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
}
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int maxn=1<<17;
struct Trie{
int tr[maxn*30][2],tot;
void ins(int x){
int p=0;
for(int i=30;i>=0;i--){
int t=x>>i&1;
if(!tr[p][t]) tr[p][t]=++tot;
p=tr[p][t];
}
}
int qry(int x){
int p=0,res=0;
for(int i=30;i>=0;i--){
int t=x>>i&1; res<<=1;
if(tr[p][t^1]) res|=1,p=tr[p][t^1];
else p=tr[p][t];
}
return res;
}
}trie;
int n,d[maxn],tot,hd[maxn];
struct Edge{
int to;
int val;
int nxt;
}edge[maxn<<1];
void adde(int u,int v,int w){
edge[++tot]=(Edge){v,w,hd[u]};
hd[u]=tot;
}
void dfs(int u,int f,int val){
d[u]=val;
for(int i=hd[u];i;i=edge[i].nxt){
int o=edge[i].to;
if(o==f) continue;
dfs(o,u,val^edge[i].val);
}
}
int main(){
rd(n);
rep(i,1,n-1){
int u,v,w; rd(u),rd(v),rd(w);
u++,v++;
adde(u,v,w);
adde(v,u,w);
}
dfs(1,0,0);
int ans=0;
rep(i,1,n){
trie.ins(d[i]);
ans=max(ans,trie.qry(d[i]));
}
printf("%d",ans);
return 0;
}
树状数组
(c_i) 维护 ([i-lowbit(i)+1,i]) 的数的和。(lowbit(x)=xand (-x))，意义是二进制表示中最低位的 (1)。
这样表示的原理是二进制拆分理论。
树状数组能解决的基本问题是单点修改区间查询。使用差分，可以解决区间修改单点查询。
如果想要解决区间修改区间查询就要维护两个树状数组了。
解决区间修改，我们肯定要使用差分。由于差分数组的前缀和数组就是原数组，所以我们可以轻松解决单点查询。
将区间查询形式化，即是求 (sumlimits_{i=1}^x sumlimits_{j=1}^i c_j)。
考虑贡献法，原式等于 (sumlimits_{i=1}^x (x-i+1)c_i=(x+1)cdot sumlimits_{i=1}^x c_i-sumlimits_{i=1}^x icdot c_i)。
使用两个树状数组分别维护 (c_i) 和 (icdot c_i) 即可。
代码：（抄自 OI Wiki）
// C++ Version
int t1[MAXN], t2[MAXN], n;
inline int lowbit(int x) { return x & (-x); }
void add(int k, int v) {
int v1 = k * v;
while (k <= n) {
t1[k] += v, t2[k] += v1;
k += lowbit(k);
}
}
int getsum(int *t, int k) {
int ret = 0;
while (k) {
ret += t[k];
k -= lowbit(k);
}
return ret;
}
void add1(int l, int r, int v) {
add(l, v), add(r + 1, -v); // 将区间加差分为两个前缀加
}
long long getsum1(int l, int r) {
return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
(getsum(t2, r) - getsum(t2, l - 1));
}