subject

meaning of the title

The number of nnn is given, and a rule of fetching is provided. From left to right, the first number is taken first, and then every time a number larger than the last one is encountered, it must be taken. Give mmm queries, each query gives a location xxx and a value hhh, which means changing the number on location xxx to hhh, and ask how many numbers can be obtained according to the retrieval rules at this time. Each inquiry is independent.

analysis

In fact, the problem is to find the strict ascending subsequence in the sequence, but since you have to select a large number, this subsequence is unique. The difficulty lies in mmm independent queries. What we want is to find out how many numbers to take out for the whole sequence. We can divide this query into how many numbers can be taken out for the sequence [1,x − 1] [1,x-1] [1,x − 1], and then how many numbers can be taken out on the sequence [x+1,n][x+1, n][x+1,n] that are larger than the maximum value of the first half.
For the first half of the period, we can maintain the number that can be taken out on the interval [1,l][1, l][1,l], and the maximum value when we get to this position i n the time of O(n)O(n)O(n).
For the second half, we will find that it is not very easy to maintain, because we need a number closest to xxx on the right, which is larger than NxN ﹣ u xNx ﹣ and this number, I chose to maintain with the line tree when filling the questions. After that, I will write blog for monotone stack maintenance ==
When using the segment tree for maintenance, because the segment tree divides the interval into two parts, the latest number of backward query is larger than NxN ﹣ nx ﹣ so when the left interval has this number, there is no need to query the right interval. When the left interval does not exist, only the right interval queries. When neither of the two intervals exists, it is proved that there is no such a larger number than NxN ﹣. Since only one interval is queried at a time, the complexity of each query is log (n) - log (n) log (n).

Code

struct Node{
    int l, r;
    int sum, minn, maxx;     //characteristic value
    int lazy;
}tree[maxn<<2];              //Open quadruple space

struct SS{
	int cnt1, cnt2;
	int maxx;
}a[maxn];

int num[maxn];               //Array of values

void build(int i, int l, int r){
    tree[i].l = l;
    tree[i].r = r;
    if(l == r){
        tree[i].minn = num[l];
        tree[i].maxx = num[l];
        return ;
    }
    
    int mid = (l+r)>>1;
    build(i<<1, l, mid);
    build(i<<1|1, mid+1, r);    //Update eigenvalue after subtree construction
    tree[i].maxx = max(tree[i<<1].maxx, tree[i<<1|1].maxx);
    tree[i].minn = min(tree[i<<1].minn, tree[i<<1|1].minn);
    return ;
}


int query_id(int i, int l, int r, int k) { //[l, r] first > k id
    if(l > r) return inf;
    int mid = (tree[i].l+tree[i].r)>>1;

    if(tree[i].l==l && tree[i].r==r){
    	if(tree[i].maxx <= k) return inf; //not have
    	else if(l == r) return l;
    	else {
    		if(tree[i<<1].maxx > k)
    			return query_id(i<<1, l, mid, k);
    		else 
    			return query_id(i<<1|1, mid+1, r, k);
    	}
    }

    
    if(mid >= r)
        return query_id(i<<1, l, r, k);
    else if(mid < l)
        return query_id(i<<1|1, l, r, k);
    else 
    	return min(query_id(i<<1, l, mid, k), query_id(i<<1|1, mid+1, r, k));
}

void geta(int n){
	int maxx = -1, cnt = 0;
	a[0].maxx = -1, a[0].cnt1 = 0;
	rep(i, 1, n+1){
		if(num[i] > maxx){
			cnt++;
			maxx = num[i];
		}
		a[i].cnt1 = cnt;
		a[i].maxx = maxx;
	}

	per(i, 1, n+1){
		int id = query_id(1, i, n, num[i]);
		a[i].cnt2 = id==inf?1:a[id].cnt2+1;
	}
}

int main()
{
	int T, n, m;
	sd(T);
	while(T--){
		sdd(n, m);
		rep(i, 1, n+1)
			sd(num[i]);
		build(1, 1, n);
		geta(n);
		rep(i, 0, m){
			int p, q;
			sdd(p, q);
			int ans = a[p-1].cnt1, maxx = a[p-1].maxx;
			if(q > maxx){
				maxx = q;
				ans++;
			}
			int id = query_id(1, p+1, n, maxx);
			ans += id==inf?0:a[id].cnt2;
			pd(ans);
		}
	}

	return 0;
}