目录
线段树分治结构
基本知识：
应用点： 当有些东西一会出现，一会又不出现时，可以使用线段树分治
方式： 维护某一个东西出现的时间段，并在线段树上打上标记，并dfs
遇到标记后，就相当于加入了这个物品。当dfs到叶子节点后，就可以得到叶子节点所代表的时间的性质
dfs返回时，若经过遇到标记的地方，需要撤回这个标记，相当于这个物品不再在答案统计内
正因如此，若是要用某个结构来维护性质，要求能够撤回
这些常见的结构有：线性运算/并查集（例题1）/dp方程式（例题2)
例题1： 模板（基础题）
题目链接：https://www.luogu.com.cn/problem/P5787
AC记录：https://www.luogu.com.cn/record/116043014
思想： 并查集维护同色关系，可以拆点或带权并查集，利用栈来维护撤回操作
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node{
int l,r,x,y;
}line[200005];
struct nod{
int ll;
int rr;
}tree[800045];
int d[200005];
stack<pair<int,bool>>s;
vector<pair<int,int>>flag[800045];
void build(int rt,int l,int r){
tree[rt].ll=l;
tree[rt].rr=r;
if(l==r){
return;
}
int mid=(l+r)/2;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
}
void updata(int rt,int cl,int cr,int flag1,int flag2){
int le=tree[rt].ll;
int ri=tree[rt].rr;
if(le>cr||ri<cl){
return;
}
if(le>=cl&&ri<=cr){
flag[rt].push_back(make_pair(flag1,flag2));
return;
}
updata(rt*2,cl,cr,flag1,flag2);
updata(rt*2+1,cl,cr,flag1,flag2);
}
//-----------------------------------------打标记线段树
int fa[400005];
int fid(int x){
if(x==fa[x]){
return x;
}
else{
return fid(fa[x]);
}
}
void he(int x, int y){
x=fid(x);
y=fid(y);
if(x==y){
return;
}
if(d[x]>d[y]) swap(x, y);
s.push(make_pair(x,d[x]==d[y]));
fa[x]=y;
if(d[x]==d[y]){
d[y]++;
}
}
void dfs(int rt,int right){
int l=tree[rt].ll;
int r=tree[rt].rr;
int o=s.size();
for(int i=0;i<flag[rt].size();i++){
int a=flag[rt][i].first;
int b=flag[rt][i].second;
if(fid(a)==fid(b)){
for(int j=l;j<=r;j++){
cout<<"No"<<endl;
}
right=0;
break;
}
else{
he(a,b+n);
he(b,a+n);
}
}//标记使用
if (right) {
if (l==r){
cout<<"Yes"<<endl;
}
else{
dfs(rt*2,right);
dfs(rt*2+1,right);
}
}
while (s.size() > o){
d[fa[s.top().first]]-=s.top().second;
fa[s.top().first]=s.top().first;
s.pop();
}
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m >> k;
build(1,0,k-1);
for(int i=1;i<=m;i++){
cin >> line[i].x>>line[i].y>>line[i].l>>line[i].r;
line[i].r--;
updata(1,line[i].l,line[i].r,line[i].x,line[i].y);
}
for(int i=1;i<=2*n;i++){
fa[i]=i;
d[i]=1;
}
dfs(1,1);
}
例题2： dp（背包）（会了就掌握题）
题目链接：http://222.180.160.110:1024/problem/5503
也可以去：https://loj.ac/p/6515
思想： 物品我一个个加入，同理我也可以一个个撤回，其实还是枚举了物品的，不过是有规律的罢了，利用cnt来记录物品进入先后关系（从而好撤回）
代码：有点难写啊
#include<bits/stdc++.h>
using namespace std;
int t,m,mod;
const int M=50005;
int tmm[M];
int L[M],R[M],ans[M];
struct node{
int tim;
int w;
int v;
};
//----------------------pack
int dp[M][505];
int cnt=0;
void clear(){
for(int i=0;i<M;i++){
for(int j=0;j<500;j++){
dp[i][j]=-0x3f3f3f3f;
}
}
dp[0][0]=0;
}
void insert(pair<int,int>now){
int x=now.first%mod;
int y=now.second;
cnt++;
for(int i=0;i<mod;i++){
dp[cnt][i]=dp[cnt-1][i];
}
for(int i=0;i<mod;i++){
if(x<=i){
dp[cnt][i]=max(dp[cnt][i],dp[cnt-1][i-x]+y);
}
else{
dp[cnt][i]=max(dp[cnt][i],dp[cnt-1][i+mod-x]+y);
}
}
}
void recall(){
for(int i=0;i<500;i++){
dp[cnt][i]=-0x3f3f3f3f;
}
cnt--;
}
int query(int l,int r){
int ret=-1;
for(int i=l;i<=r;i++){
ret=max(ret,dp[cnt][i]);
}
return ret;
}
//---------------------tree
struct nod{
int ll;
int rr;
}tree[4*M];
vector<pair<int,int>>flag[4*M];
void build(int rt,int l,int r){
tree[rt].ll=l;
tree[rt].rr=r;
if(l==r){
return;
}
int mid=(l+r)/2;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
}
void updata(int rt,int cl,int cr,int weight,int value){
int le=tree[rt].ll;
int ri=tree[rt].rr;
if(le>cr||ri<cl){
return;
}
if(le>=cl&&ri<=cr){
flag[rt].push_back(make_pair(weight,value));
return;
}
updata(rt*2,cl,cr,weight,value);
updata(rt*2+1,cl,cr,weight,value);
}
void solve(int rt){
int l=tree[rt].ll;
int r=tree[rt].rr;
int sz=flag[rt].size();
for(int i=0;i<sz;i++){
insert(flag[rt][i]);
}
if(l^r){
solve(rt*2);
solve(rt*2+1);
}
else if(L[l]^-1){
ans[l]=query(L[l],R[r]);
}
for(int i=0;i<sz;i++){
recall();
}
}
//---------------------------tree
int main(){
ios::sync_with_stdio(false);
cin >> t;
cin >> m >> mod;
clear();
memset(L,-1,sizeof(L));
build(1,1,m);
deque<node>q;
for(int i=1;i<=m;i++){
string op;
cin >> op;
int w,v;
if(op[0]=='I'&&op[1]=='F'){
cin >> w >> v;//前面放
node Q=(node){i,w,v};
q.push_front(Q);
}
else if(op[0]=='I'&&op[1]=='G'){
cin >> w >> v;//后面放
node Q=(node){i,w,v};
q.push_back(Q);
}
else if(op[0]=='D'&&op[1]=='F'){//删除前面
node Q=q.front();
q.pop_front();
updata(1,Q.tim,i-1,Q.w,Q.v);
}
else if(op[0]=='D'&&op[1]=='G'){//删除后面
node Q=q.back();
q.pop_back();
updata(1,Q.tim,i-1,Q.w,Q.v);//区间标记
}
else if(op[0]=='Q'&&op[1]=='U'){
int l,r;
cin >> l >> r;//w和mod在l-r区间内最强武力值
L[i]=l;
R[i]=r;
}
}
while(q.size()){
node Q=q.front();
q.pop_front();
updata(1,Q.tim,m,Q.w,Q.v);//永远不会消失的要注意添加
}
solve(1);
for(int i=1;i<=m;i++){
if(L[i]^-1){
cout<<ans[i]<<endl;
}
}
}