云南网站设计方案,仪征建设局网站,系统软件,珠海建网站的联系方式本题注意离散化的时候可能会出现区间串联情况#xff0c;比如
[1,10] [5,10] [1,4] 和 [1,10] [6,10] [1,4] 直接离散化的话两者一样#xff0c;但是实际上是不一样的
解决办法是你在相邻的差不是1的数对中再插一个数就好了 离线区间染色 查询根节点
#includeiostrea… 本题注意离散化的时候可能会出现区间串联情况比如
[1,10] [5,10] [1,4] 和 [1,10] [6,10] [1,4] 直接离散化的话两者一样但是实际上是不一样的
解决办法是你在相邻的差不是1的数对中再插一个数就好了 离线区间染色 查询根节点
#includeiostream
#includevector
#includecstring
#includealgorithm
using namespace std;const int N 1e510,inf 0x3f3f3f3f;
struct Segment{int l,r;int id;
}tr[N3];
bool st[N];
vectorintv;
vector pairint,int op;
int m;
int findx(int x){return lower_bound(v.begin(),v.end(),x)-v.begin();}void pushdown(int u){if(tr[u].id){tr[u1].id tr[u1|1].id tr[u].id;tr[u].id 0;}
}void build(int u,int l,int r){tr[u] {l,r,0};if(lr)return;int mid lr1;build(u1,l,mid),build(u1|1,mid1,r);
}void modify(int u,int l,int r,int c){if(tr[u].lltr[u].rr){tr[u].id c;return;}pushdown(u);int mid tr[u].ltr[u].r1;if(lmid)modify(u1,l,r,c);if(rmid)modify(u1|1,l,r,c);}int query(int u){if(tr[u].id){if(st[tr[u].id])return 0;return st[tr[u].id] 1;}if(tr[u].ltr[u].r)return 0;return query(u1)query(u1|1);
}int main()
{int _;cin_;while(_--){v.clear(),op.clear();v.push_back(-inf),op.push_back({0,0});memset(st,0,sizeof st);cinm;for(int i1;im;i){int l,r;cinlr;v.push_back(l),v.push_back(r);op.push_back({l,r});}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int vlen v.size();for(int i1;i1vlen;i)if(v[i1]-v[i]1)v.push_back(v[i1]-1);sort(v.begin(),v.end());build(1,1,v.size()-1);for(int i1;im;i){int l findx(op[i].first),r findx(op[i].second);modify(1,l,r,i);}coutquery(1)\n;}
}
