[learning notes] differential constraint

The perfect combination of graph theory and inequality .

• If you find the maximum value of the difference between two variables , Then find the shortest path , Form like $x_i+d\ge x_j$
• If you find the minimum value of the difference between two variables , Then find the longest way , Form like $x_i+d\le x_j$

Talk nonsense

Wannafly challenge round 9E - Group by group

There's a long one for n Sequence of numbers A, Among them is m There are two restrictions , There are two conditions ：

1、 For interval [l,r], Its interval elements are bitwise or equal to x.
2、 For interval [l,r], Its interval elements are bitwise AND and equal to x.

Find a sequence of numbers A, To satisfy a given m Conditions , Make sure there's a solution .

1<=n,m<=10^5, 1<=l<=r<=n, 0<=x<2^20

sol： Obviously, in terms of position . Then find the shortest path .

wait … direct spfa Too slow will T .

We can make the upper bound a little smaller .

For or for 0 Arithmetic , We know s[l~r]=0 .

For prefixes and sum[i] , hypothesis s[1~i] Yes x individual 0 . that sum[i]<=i-x .

We connect one directly from the source i-x The edge of , It can effectively reduce the number of iterations .

[POI2015] PUS

POI

First of all, the complexity problem is not considered , This is a difference constraint .

Then consider optimizing .

One is when building a map , The problem of too many edges , We use the segment tree to optimize the drawing .

The second problem is that the data is too large to run . We Optimize according to the particularity of the graph .

First of all d[i]=x , We throw away the negative side , That is, only the lower bound is preserved , Final back inspection .

This is the right side .

Second, if you have a positive ring , Output has no solution .

direct DAG Just run topology sorting .