网站首页html代码,海南省做购房合同网站,wordpress关闭伪静态,长沙百度推广排名正题 题目大意
无限长的010101序列#xff0c;每次进行一个操作
区间内赋值为000区间内赋值为111区间取反
求第一个000的位置 解题思路
离散化#xff08;储存每个区间的左右端点和他们加一之后的值#xff09;后可以用线段树储存第一个000和第一个111的位置。然后区间取…正题 题目大意
无限长的010101序列每次进行一个操作
区间内赋值为000区间内赋值为111区间取反
求第一个000的位置 解题思路
离散化储存每个区间的左右端点和他们加一之后的值后可以用线段树储存第一个000和第一个111的位置。然后区间取反时就交换两个值并且让lazylazylazy标记同样取反即可
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510;
ll n,m,l[N],r[N],op[N],a[N];
ll minw[N*4],minb[N*4],lazy[N*4];
void Downdata(ll x,ll l,ll r,ll op){if(op3lazy[x]){if(lazy[x]1)lazy[x]2;else if(lazy[x]2)lazy[x]1;else if(lazy[x]3)lazy[x]0;}else lazy[x]op;if(op1)minw[x]l,minb[x]n1;else if(op2)minw[x]n1,minb[x]l;else swap(minw[x],minb[x]);return;
}
void Change(ll x,ll L,ll R,ll l,ll r,ll op){if(LlRr){Downdata(x,l,r,op);return;}ll mid(LR)1;if(lazy[x]){Downdata(x*2,L,mid,lazy[x]);Downdata(x*21,mid1,R,lazy[x]);lazy[x]0;}if(rmid)Change(x*2,L,mid,l,r,op);else if(lmid)Change(x*21,mid1,R,l,r,op);else Change(x*2,L,mid,l,mid,op),Change(x*21,mid1,R,mid1,r,op);minw[x]min(minw[x*2],minw[x*21]);minb[x]min(minb[x*2],minb[x*21]);return;
}
int main()
{scanf(%lld,m);for(ll i1;im;i){scanf(%lld%lld%lld,op[i],l[i],r[i]);a[n]l[i];a[n]r[i];a[n]l[i]1;a[n]r[i]1;}a[n]1;sort(a1,a1n);nunique(a1,a1n)-a-1;a[n1]a[n]1;for(ll i1;iN*4;i)minb[i]minw[i]n1;Change(1,1,n,1,n,2);for(ll i1;im;i){l[i]lower_bound(a1,a1n,l[i])-a;r[i]lower_bound(a1,a1n,r[i])-a;Change(1,1,n,l[i],r[i],op[i]);printf(%lld\n,a[minb[1]]);}
}
