Codeforces Round ＃474 (Div. 1 + Div. 2) - C, F

https://codeforces.com/contest/960

F. Pathwalks

The question
Given n A little bit ,m Directed graph of strip edge , Each edge has a weight $w_i$.
Find a path （ It may pass through a certain point several times ）, All edges in the path are connected in the order of input to the edges , And the weight strictly rises .
In all satisfied paths , Find the one with the most sides , Output the number of sides .

$(1\le n\le 10^5,1\le m\le 10^5,0\le wi\le 10^5)$

Ideas
Because all edges in the path are connected according to the input order , The weight rises strictly , So every input edge , You can transfer to get the longest length of all paths ending with this side .
For a given edge $x,y,w$, Find all pointing nodes x The edge of , Use the weight in these edges to be less than w To transfer .

use f[i] Express , By the side i The longest end satisfies the length of the path .

So that is , Find the pointing node x The ownership value of is less than w The edge of , Use these side f[i] Maximum shift .

But traverse all points x The edge finding weight of is less than w Of f[i] To transfer the complexity is too high , When there is 1e5 When two edges point to two points , Each given edge traverses all other edges , Complexity is n^2 Of . We need to find ways to optimize .

It can be seen that , Each time, only the weight is less than w In the side of the road , maximal f[i] To transfer , Sure Create a tree array for each node , The weights of all edges pointing to this point w As a subscript ,f[i] As the corresponding value . Every time I look for [1, w-1] In weight f[i] The maximum of , The tree array finds the maximum value of the interval ,O(logn).

But pay attention to the weight wi May be 0, That is, the subscript in the tree array 0 The position of also has a corresponding value , But when inserting and asking , Unable to deal with 0 The situation of , So we need to make an offset , Set the weights of all edges +1.

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
map<int, int> c[N];

int lbit(int x){
    
	return x & -x;
}

void update(int k, int x, int y)
{
    
	for(int i=x;i<=100000;i+=lbit(i)){
    
		c[k][i] = max(c[k][i], y);
	}
}

int query(int k, int x)
{
    
	int maxa = 0;
	for(int i=x;i>=1;i-=lbit(i)){
    
		maxa = max(maxa, c[k][i]);
	}
	return maxa;
}

signed main(){
    
	Ios;
	cin >> n >> m;
	
	int ans = 0;
	while(m--)
	{
    
		int x, y, z; cin >> x >> y >> z;
		z ++;
		
		int maxa = query(x, z-1);
		
		update(y, z, maxa+1);
		
		ans = max(ans, maxa + 1);
	}
	cout << ans;
	
	return 0;
}

Clever tree array ！

In fact, when you see the weight size is only 1e5 You should see the clue when , If the processing method has nothing to do with the weight , It can drive to 1e9, And this question only 1e5, Then we need to think about whether to establish a tree array on the numerical range ！

---

C. Subsequence Counting

The question
For a length of n For a series of numbers , Its subsequences are $2^n-1$ individual .
Now there is a sequence , After the following operations, only X Subsequence ：

• For a subsequence , If the maximum value of elements in the sequence - The minimum value of the element ≥ d, Then the subsequence will be deleted .

give X and d, Construct a satisfying sequence , Output length n And the elements ai.

$1\le X,d\le 10^9$,
$1\le n\le 10^4,1\le ai<10^{18}$

Ideas
Think of special circumstances ！！

For a sequence 1 1 1 1 d+1 d+1 d+1 d+1 Come on , The first half and the second half of the sequence will not produce a resultant subsequence , Because once 1 and 1+d At the same time , This subsequence will be deleted . So the first and second paragraphs don't affect each other .
therefore , The sum of the number of subsequences generated by the left and right segments is the number of subsequences of the whole sequence .

that , The whole sequence can be constructed in this way ：1 1 ... 1, 1+d 1+d ... 1+d, 1+2d 1+2d ... 1+2d, ..., Put together its subsequence number binary X that will do .

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
    
	Ios;
	int x, d; cin >> x >> d;
	
	bitset<30> f(x);
	
	int t = 0;
	vector<int> v;
	for(int i=0;i<30;i++)
	{
    
		if(!f[i]) continue;
		int cnt = 1<<i;
		for(int j=1;j<=i;j++) v.push_back(t*d + 1);
		t ++;
		v.push_back(t*d + 1), t ++;
	}
	cout << v.size() << endl;
	for(int x : v) cout << x << " ";
	
	return 0;
}