网站更换ip 备案,wordpress插件更新失败,商务网站建设与维护 试题,问政烟台网站本题注意离散化的时候可能会出现区间串联情况#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;}
}
