Summary of loose knowledge points (hold shift)

There are a few little tricks that it wouldn't be appropriate to dedicate an entire blog to, so let's put them all here.

inverse order pair (math.)

The tree array approach on the exam is obviously better to write than any other.

To consider the contribution of each element to the answer, we need to know how many elements before it are larger than it.

We just need to maintain a tree-like array of weights that we can use when enumerating to the\(i\) The time to query the current tree array of elements how many larger than it, in order to facilitate the processing of our inverted enumeration, which is equivalent to the order of the pairs, the convenience of tree arrays to calculate the answer.

After each accumulation just add the current element to the tree array.

for(int i=n;i>=1;i--) 
{
	ans+=ask(a[i]-1);	
	add(a[i],1);
}

binary grouping

If we have a bunch of numbers, we now have to divide them into two groups multiple times, requiring that for every two numbers there is at least one time in a different group.

We consider binary, and for each bit, take all the digits this bit as\(0\) s are divided into groups for\(1\) s into groups, it can be shown that this must satisfy the above condition.

simple proof

For two different numbers\(i,j\), their binary expressions must be different in at least one bit,. So by the above grouping method there must be at least one time when they are not inside the same group.

Testify to the end.

The grouping process is simple, so give an example problem.

[GXOI/GZOI2019] Travelers

Binary group all cities of interest, and then get two virtual points, a start point and an end point, and connect each of the two groups of points to the\(0\) The edge of the edge right and then just run the shortest circuit.

#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 >;
	}
};
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;
	({0,0});
	while(!())
	{
		int u=().id;
		();
		if(vis[u])continue;
		vis[u]=1;
		for(auto i : G[u])
		{
			int y=,v=;
			if(dis[u]+v<dis[y])
			{
				dis[y]=dis[u]+v;
				if(!vis[y])
				({dis[y],y});
			}
		}
	}
}
signed main()
{
//	freopen("","r",stdin);
//	freopen("","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;
}

In fact, a simple thought reveals that there are similar groupings such as trinary quadrature and the like, but these are not commonly used either, but a little bit of knowledge is a little bit of knowledge.

High-dimensional prefixes and

This is not a high-dimensional prefix sum for tree array interval operations (who uses that one?), but a dimension.

analogiesABC366DFor this question, the computation of one to three dimensional prefixes and arrays is given first:

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];

Anyone who knows a little math can already see the pattern. Carrying out\(n\) dimensional prefix sums, for each dimension of the prefix sum array, we separately pair the\(1\sim n\) subscripts for\(-1\) The symbol is a plus sign if the number of modifications is a Vicky number, otherwise it is a minus sign.

It is easy to find out that if the number of modifications is\(m\)The total number of changes required is\(n\choose m\) times. Therefore too high-dimensional ones are generally not used often enough to understand.