有一些小 trick，专门用一整篇博客来写不太合适，所以都放在这里吧。
逆序对
考试的时候树状数组做法显然比其他的都好写。
考虑每个元素对答案的贡献，我们需要知道在它之前有多少元素比它大。
我们只需要维护一个权值树状数组，在枚举到 \(i\) 的时候查询当前树状数组中的元素有多少比它大，为了方便处理我们倒序枚举，这样相当于求顺序对，方便树状数组计算答案。
每次累加以后只需要把当前元素加进树状数组即可。
for(int i=n;i>=1;i--)
{
ans+=ask(a[i]-1);
add(a[i],1);
}
二进制分组
如果我们有一堆数字，现在要把它们多次分成两组，要求对于每两个数字都至少有一次分在不同的组。
我们考虑二进制，对于每一位，把所有数字这一位为 \(0\) 的分成一组，为 \(1\) 的分成一组，可以证明这样一定能满足上述条件。
简单证明
对于两个不同的数字 \(i,j\)，它们的二进制表达一定至少有一位是不同的，。因此按照上述分组方法一定会至少有一次不在同一组里面。
证毕。
分组的过程很简单，所以给一道例题。
把所有感兴趣的城市进行二进制分组，然后搞两个虚拟点，一个起点一个终点，分别给两组点连 \(0\) 边权的边，然后跑最短路即可。
可爱的代码
#include<bits/stdc++.h>
#define int long long
inline int read()
{
int w=1,s=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return w*s;
}
using namespace std;
const int maxn=1e6+10;
int T,n,m,k;
int a[maxn];
struct no
{
int y,v;
};
vector<no> G[maxn];
struct dij
{
int y,id;
inline friend bool operator < (dij x,dij y)
{
return x.y>y.y;
}
};
int dis[maxn];
bool vis[maxn];
void dijkstra()
{
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
priority_queue<dij> q;
dis[0]=0;
q.push({0,0});
while(!q.empty())
{
int u=q.top().id;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto i : G[u])
{
int y=i.y,v=i.v;
if(dis[u]+v<dis[y])
{
dis[y]=dis[u]+v;
if(!vis[y])
q.push({dis[y],y});
}
}
}
}
signed main()
{
// freopen("tourist.in","r",stdin);
// freopen("tourist.out","w",stdout);
cin>>T;
while(T--)
{
n=read(),m=read(),k=read();
for(int i=0;i<=n;i++)G[i].clear();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),v=read();
G[x].push_back({y,v});
}
for(int i=1;i<=k;i++)a[i]=read();
int ans=0x3f3f3f3f3f3f;
for(int i=0;(1<<i)<=n;i++)
{
G[0].clear();
for(int j=1;j<=k;j++)
{
if(a[j]&(1<<i))G[0].push_back({a[j],0});
else G[a[j]].push_back({n+1,0});
}
dijkstra();
ans=min(ans,dis[n+1]);
for(int j=1;j<=k;j++)
if((!(a[j]&(1<<i))))G[a[j]].pop_back();
G[0].clear();
for(int j=1;j<=k;j++)
{
if(!(a[j]&(1<<i)))G[0].push_back({a[j],0});
else G[a[j]].push_back({n+1,0});
}
dijkstra();
ans=min(ans,dis[n+1]);
for(int j=1;j<=k;j++)
if((a[j]&(1<<i))) G[a[j]].pop_back();
}
printf("%lld\n",ans);
}
return 0;
}
其实简单一想就能发现类似的还有三进制四进制之类的分组，不过这些也不常用，但知道一点是一点。
高维前缀和
这个不是树状数组区间操作的高维前缀和（这个谁用啊），而是维度。
类比ABC366D这道题，先给出一到三维前缀和数组的计算方法：
\[sum_i=a_i+sum_{i-1} \]\[sum_{i,j}=a_{i,j}+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1} \]\[sum_{i,j,k}=a_{i,j,k}+sum_{i,j,k-1}+sum_{i,j-1,k}+sum_{i-1,j,k}-sum_{i,j-1,k-1}-sum_{i-1,j,k-1}-sum_{i-1,j-1,k}+sum_{i-1,j-1,k-1} \]代码版(复制用)
sum[i]=a[i]+sum[i-1];
sum[i][j]=a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
sum[i][j][k]=a[i][j][k]+sum[i][j][k-1]+sum[i][j-1][k]+sum[i-1][j][k]-sum[i][j-1][k-1]-sum[i-1][j][k-1]-sum[i-1][j-1][k]+sum[i-1][j-1][k-1];
稍微懂一点数学的人都已经能看出来规律了。进行 \(n\) 维前缀和的时候，对于前缀和数组的每一维，我们分别对 \(1\sim n\) 个下标进行 \(-1\) 的修改，如果修改个数维奇数，则符号为加号，否则为减号。
容易发现若修改个数为 \(m\)，则共需要修改 \(n\choose m\) 次。因此太高维的一般也不常用，了解即可。
标签：总结,知识点,ch,树状,int,sum,数组,dis From： https://www.cnblogs.com/Lydic/p/18352951