F. SUM and REPLACE(线段树+思维+剪枝)

题目大意：
先定义一个 $D\left(i\right):i的因子个数$D(i):i的因子个数,现在给你一个序列，你要做两种操作，操作 $1:将[l,r]中的ai用d\left(ai\right)$1:将[l,r]中的ai用d(ai)替换。操作 $2:$2:求区间 $[l,r]$[l,r]所有数字和。
思路：
这题与D. The Child and Sequence是一个套路，注意到将 $d\left(1e6\right)$d(1e6)到 $1or2$1or2，不会超过 $10$10次(很显然次数特别少)，所以可以可以单点修改，维护一个最大值，当最大值 <=2，这个区间可以不管了，因为 $d\left(1\right)=1,d\left(2\right)=2$d(1)=1,d(2)=2。所以粗略的估计总复杂度不会超过 $O\left(m10logm\right)$O(m10logm)。
总结：有点体会到线段树套路题了。单点修改的时候 $max$max也要修改(一开始忘记了。)。
代码：

#include<iostream>
using namespace std;

typedef long long int ll;
const int maxn = 3e5 + 10;
const int maxx = 1e6 + 10;
int ans[maxx];
struct seg{
	int l,r;
	ll s,m;
	seg(){s = 0,m = 0;}
	seg(int a,int b):l(a),r(b){}
}tree[maxn << 2];
void build(int id,int l,int r){
	tree[id] = {l,r};
	if(l == r){
		scanf("%lld",&tree[id].s);
		tree[id].m = tree[id].s;
		return ;
	}
	int mid = l + r >> 1;
	build(id << 1,l,mid);
	build((id << 1) + 1,mid + 1 ,r);
	tree[id].s = tree[id << 1].s + tree[(id << 1) + 1].s;
	tree[id].m = max(tree[id << 1].m ,tree[(id << 1) + 1].m);
}
ll query(int id,int l,int r){
	if(tree[id].l >= l && tree[id].r <= r){
		return tree[id].s;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	ll ans = 0;
	if(r <= mid)return ans += query(id << 1,l,r);
	else if(l > mid) return ans += query((id << 1) + 1,l,r);
	else return ans += query(id << 1,l,r) + query((id << 1) + 1,l,r);
}
void update(int id,int l,int r){
	if(tree[id].m <= 2)return;
	if(tree[id].l >= l && tree[id].r <= r && tree[id].l == tree[id].r){
		tree[id].m = tree[id].s = ans[tree[id].s];
		return ;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	if(r <= mid) update(id << 1,l,r);
	else if(l > mid) update((id << 1) + 1,l,r);
	else update(id << 1,l,r) ,  update((id << 1) + 1,l,r);
	tree[id].s = tree[id << 1].s + tree[(id << 1) + 1].s;
	tree[id].m = max(tree[id << 1].m ,tree[(id << 1) + 1].m);
}
void solved(){
	for(int i = 1; i <= 1e6; i++){
        for(int j = i; j <= 1e6; j += i)
            ans[j]++;
    }
	int n,m;cin>>n>>m;
	build(1,1,n);
	while(m--){
		int ins,l,r;scanf("%d%d%d",&ins,&l,&r);
		if(ins == 2){
			printf("%lld\n",query(1,l,r));
		}
		if(ins == 1){
			update(1,l,r);
		}
	}
}
int main(){
	solved();
	return 0;
} 

Laptop.


思路：
一种很容易想到的做法，先对第一维升序，然后枚举每个点，找到一个大于他的数即可(在第二维中),时间复杂度 $O\left(n^2\right)$O(n2)，显然 $1e5$1e5并不会让你这么轻易的过去，所以我们考虑优化。因为第一维已经升序，我们不用再考虑，我们只需要考虑第二维，对于第 $i$i个点的第二维，事实上我们只要在区间 $[i+1,n]$[i+1,n]找到一个比他大的数即可。所以问题就转化成了区间 $MRQ$MRQ问题，用线段树维护一下就解决了。整体时间复杂度 $O\left(nlogn\right)$O(nlogn)。
代码：

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

#define fi first
#define se second
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int ,int> pii;
const int maxn = 1e5 + 10;
pii a[maxn];
bool cmp(pii a,pii b){
	return a.fi < b.fi;
}
struct seg{
	int l,r;
	ll v,m;
	seg(){}
	seg(int a,int b):l(a),r(b){}
}tree[maxn <<  2];
int tot = 1;
void build(int rt,int l,int r){
	tree[rt] = {l,r};
	if(l == r){
		tree[rt].m = tree[rt].v = a[tot++].se;
		return ;
	}
	int mid = l + r >> 1;
	build(rt << 1,l,mid);
	build((rt << 1) + 1,mid + 1,r);
	tree[rt].m = max(tree[rt << 1].m,tree[(rt << 1) + 1].m);
}
int query(int rt,int l,int r){
	if(tree[rt].l >= l && tree[rt].r <= r){
		return tree[rt].m;
	}
	int mid = tree[rt].l + tree[rt].r >> 1;
	if(r <= mid) return query(rt << 1,l,r);
	else if(l > mid) return query((rt << 1) + 1,l,r);
	else return max(query(rt << 1,l,r),query((rt << 1) + 1,l,r));
}
void solved(){
	int n;cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i].fi>>a[i].se;
	}
	sort(a + 1,a + 1 + n,cmp);
	build(1,1,n);
	int ans = 0;
	for(int i = 1; i < n; i++){
		if(a[i].se < query(1,i + 1,n))ans++;
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
}