mle了30来发 花了两个半小时 终于找到bug a了这题
a了之后不知道该开心还是该骂自己sb
题目思路
题目挺简单的就是区间染色 最后统计总区间的颜色个数
因为区间数不算大 但是区间的端点值可以很大
所以要对区间进行离散化
离散化的时候要注意两个点之间差值大于1时要插入一个他们中间的值进去
具体解释可以看这个博客
https://blog.csdn.net/zezzezzez/article/details/80230026
懂了这些之后就是套离散化和区间染色板子的板子题了
离散化板子
https://blog.csdn.net/daydreamer23333/article/details/107264305
区间染色板子
void build(){memset(tree,0,sizeof(tree));
}
// 有这样的情况，底层有规定颜色，那么就不能用memset而是要用for循环
void build(int color){for(int i = 1;i <= len;i++){tree[i] = color;}
}
void update_range(int node, int l, int r, int L, int R, int add) {if (l <= L && r >= R) {lz[node] = add;tree[node] = add; // 更新方式return;}push_down(node, L, R);int mid = (L + R) / 2;if (mid >= l) update_range(node * 2, l, r, L, mid, add);if (mid < r) update_range(node * 2 + 1, l, r, mid + 1, R, add);if (tree[node * 2] == tree[node * 2 + 1]) {tree[node] = tree[node * 2];}else {tree[node] = -1;}
}void push_down(int node） {if (lz[node]) {int mid = (l + r) / 2;lz[node * 2] = lz[node];lz[node * 2 + 1] = lz[node];tree[node * 2] = lz[node];tree[node * 2 + 1] = lz[node];lz[node] = 0;}
}void query_range(int node, int L, int R, int l, int r) {if (l <= L && r >= R) {if (tree[node] == 0) return;if (tree[node] == -1) {push_down(node, L, R);int mid = (L + R) / 2;if (mid >= l) query_range(node * 2, L, mid, l, r);if (mid < r) query_range(node * 2 + 1, mid + 1, R, l, r);}else {if (color[tree[node]] == 0) {ans++;color[tree[node]] = 1;}}return;}push_down(node, L, R);int mid = (L + R) / 2;if (mid >= l) query_range(node * 2, L, mid, l, r);if (mid < r) query_range(node * 2 + 1, mid + 1, R, l, r);
}
ac代码
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#define pi 3.1415926535898
#define ll long long
#define lson rt<<1
#define rson rt<<1|1
#define eps 1e-6
#define ms(a,b) memset(a,b,sizeof(a))
#define legal(a,b) a&b
#define print1 printf("111\n")
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1000000007;
//998244353
int t[maxn<<2],lz[maxn<<2];
int color[maxn],n,ans;
vector<int>vec;
int li[maxn],ri[maxn];int getid(int x)
{return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;
}void build(int rt,int l,int r)
{lz[rt]=0;t[rt]=0;if(l==r){return;}int mid=(l+r)>>1;build(lson,l,mid);build(rson,mid+1,r);
}void push_down(int rt)
{if(lz[rt]){lz[lson]=lz[rt];lz[rson]=lz[rt];t[lson]=lz[rt];t[rson]=lz[rt];lz[rt]=0;}
}void update(int rt,int l,int r,int L,int R,int v)
{if(L<=l&&r<=R){t[rt]=v;lz[rt]=v;return;}push_down(rt);int mid=(l+r)>>1;if(mid>=L)update(lson,l,mid,L,R,v);if(mid<R)update(rson,mid+1,r,L,R,v);if(t[lson]==t[rson])t[rt]=t[lson];elset[rt]=-1;
}void query(int rt,int l,int r,int L,int R)
{if(L<=l&&r<=R){if(t[rt]==0)return;if(t[rt]==-1){push_down(rt);int mid=(l+r)>>1;if(mid>=L)query(lson,l,mid,L,R);if(mid<R)query(rson,mid+1,r,L,R);}else{if(color[t[rt]]==0){ans++;//printf("t %d\n",t[rt]);color[t[rt]]=1;}}return;}push_down(rt);int mid=(l+r)>>1;if(mid>=L)query(lson,l,mid,L,R);if(mid<R)query(rson,mid+1,r,L,R);
}int main()
{int t;scanf("%d",&t);while(t--){vec.clear();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&li[i],&ri[i]);vec.push_back(li[i]);vec.push_back(ri[i]);}sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());int te=vec.size();//这里一定要注意 for(int i=1;i<te;i++)//如果直接写vec.size()的话会mle 坑了我两个小时{if(vec[i]-vec[i-1]>1)vec.push_back((vec[i-1]+1));}sort(vec.begin(),vec.end());build(1,1,vec.size());int cot=0;for(int i=1;i<=n;i++){int x1=getid(li[i]);int y1=getid(ri[i]);int ends=vec.size();update(1,1,ends,x1,y1,i);}for(int i=1;i<=n;i++)color[i]=0;ans=0;query(1,1,vec.size(),1,vec.size());printf("%d\n",ans);}
}