讲解视频在此 ：https://www.cometoj.com/live/10614/replay?replayId=13896&page=3

Problem 1st : BZOJ4432 并查集、对偶图

分析 ： 如果题目是可以离线做的话，直接将顺着删边抓化为倒着添加边，并查集维护即可。但是这题是强制在线的，所以把原图抓化成对偶图，这篇博客讲的很清楚 https://blog.csdn.net/Jasmineaha/article/details/86603813
人家写的代码也比我简洁多了.......
code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
int fa[maxn*maxn],ran[maxn*maxn],id[maxn][maxn];
int Find(int x){return fa[x]=(fa[x]==x?x:Find(fa[x]));}
void Union(int x,int y)
{
	int fx=Find(x),fy=Find(y);
	if(ran[fx]>=ran[fy]) {
		fa[fy]=fx;
		ran[fx]+=ran[fy];
	} 
	else {
		fa[fx]=fy;
		ran[fy]+=ran[fx];
	}
}
int main()
{
	int n,k,flag=0,num=0;
	scanf("%d%d",&n,&k);
	for(int i=0;i<maxn*maxn;i++) fa[i]=i,ran[i]=0;
	for(int i=1;i<n;i++) for(int j=1;j<n;j++) id[i][j]=++num;
	while(k--)
	{
		int a,b,c,d,x,y;
		char op1[3],op2[3];
		scanf("%d%d%s%d%d%s",&a,&b,op1+1,&c,&d,op2+1);
		if(!flag) {
			if(op1[1]=='N') {
				x=id[a-1][b],y=id[a][b]; 
				if(Find(x)==Find(y)) flag=1,printf("NIE\n"); 
				else flag=0,printf("TAK\n");
			} 
			else {
				x=id[a][b-1],y=id[a][b];
				if(Find(x)==Find(y)) flag=1,printf("NIE\n"); 
				else flag=0,printf("TAK\n");
			}
		}
		else {
			if(op2[1]=='N') {
				x=id[c-1][d],y=id[c][d];
				if(Find(x)==Find(y)) flag=1,printf("NIE\n"); 
				else flag=0,printf("TAK\n");
			} 
			else {
				x=id[c][d-1],y=id[c][d];
				if(Find(x)==Find(y)) flag=1,printf("NIE\n"); 
				else flag=0,printf("TAK\n");
			}
		}
		Union(Find(x),(Find(y)));
	}		
	return 0;
}

Problem 2nd : 思维

Description
有n个东西，每个东西有两个属性ai和bi，每个东西你只能选择1个属性。你需要选择A个a属性以及B个b属性，使得属性和最大。

按照a排序，枚举最后一个a的位置，之后肯定都是选b，之前一定都被选了，其中被选了a的是那些b − a较小的。



Problem 3rd : 线段树


分析 ：其实CF的官方tutorial讲的足够清楚了。但还是分享一篇讲的较清楚的中文博客 ：https://blog.csdn.net/berrykanry/article/details/77053476

——————————————————————分界线—————————————————————————————

下面是摘录的关键部分 ：
对于区间和这个问题，利用线段树就可以轻松解决，但是问题是如何对一段区间内的每个数取模？这个线段树是做不到的，那么来考虑取模的意义和影响。

对于每个数 x，对 y 取模后，x mod y 的值必然比 y 小。如果 y < x/2，那么 x 就会变得小于 x/2，如果 y 大于 x/2，即 x 剩下的部分比 x/2 少，那么取模后 x 也会变得比 x/2 小。所以不难得出，对于一个数 x，有效的取 mod 最多进行 logx 次，也就是说一共最多只会进行nlogn次取模，所以即使暴力对所有的数取模，时间复杂度也是可以接受的。

对于一段区间，如果取模的数比这段区间所有的数都大，那取模就是没有意义的。也就是说，如果取模的数比区间的最大值还大，那么就不需要取模了。

所以我们在线段树里再记录一个区间最大值，如果取模的数大于最大值，就不进行此次操作，如果小于最大值，就暴力取模。

——————————————————————分界线—————————————————————————————

感觉这道题写了之后对线段树的理解更深刻了一点，各种奇怪的修改和维护区间的某个属性的题目如果满足下面两个条件是可以放心用线段树的：
1.修改操作具备某种性质使得这种修改最多执行一定的次数(可以是常数[ eg.开根号 ]，可以是log(该数)级别[ eg.这道题 ])；
2. 要维护的东西满足区间可加性
code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll max(ll a,ll b){return a>b?a:b;}
ll a[maxn];
struct ST {
	ll maxv,sum;
	int l,r;
}t[maxn<<2];
void push_up(int p)
{
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].maxv=max(t[p*2].maxv,t[p*2+1].maxv);
}
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) {
		t[p].maxv=t[p].sum=a[l]; return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid); build(p*2+1,mid+1,r);
	push_up(p);
}
void setvalue(int p,int k,ll x)
{
	if(t[p].l==t[p].r) {
		t[p].maxv=t[p].sum=x; return;
	}	
	int mid=(t[p].l+t[p].r)>>1;
	if(k<=mid) setvalue(p*2,k,x);
	else setvalue(p*2+1,k,x);
	push_up(p);
}
void update(int p,int l,int r,ll x)
{
	if(t[p].maxv<x) return;
	if(t[p].l==t[p].r) {
		t[p].sum%=x,t[p].maxv%=x; return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) update(p*2,l,r,x);
	if(r>mid) update(p*2+1,l,r,x);
	push_up(p);
}
ll query(int p,int l,int r)
{
	if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
	int mid=(t[p].l+t[p].r)>>1;
	ll ans=0;
	if(l<=mid) ans+=query(p*2,l,r);
	if(r>mid) ans+=query(p*2+1,l,r);
	return ans;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op;
		scanf("%d",&op);
		if(op==1) {
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%lld\n",query(1,l,r));
		}
		else if(op==2) {
			int l,r,x;
			scanf("%d%d%lld",&l,&r,&x);
			update(1,l,r,x);
		}
		else {
			int k,x;
			scanf("%d%lld",&k,&x);
			setvalue(1,k,x);
		}
	}
	return 0;
}  

Problem 4th : 洛谷P4097 [HEOI2013]Segment 李超线段树

题目链接 : https://www.luogu.com.cn/problem/P4097
分析 ： 对于每一个区间，（拙劣描述开始）想象有光从正上方照下来，维护被阳光照到的最长的(即未被别的线段从上面压着)线段的性质。加入一个新线段时(add函数)，先判断他覆盖的区间是否被update过，如果没有，直接把该线段的属性赋予这个区间。如果已经被赋值过了，找到区间记录的线段和新线段交点，交点不在的一侧，可以直接维护(选取新旧线段中更高的)，交点所在一侧，不断递归下去，直到单点。这一部分复杂度为log2(新线段长度)。总复杂度约为n*log2(n)*log2(n)级别
code :