2018-10-03 19:14:10

#include<cstdio>
#include<cctype>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>
#define IT set<node>::iterator

{
int x=0;char c=getchar();
while(!isdigit(c))
{
c=getchar();
}
while(isdigit(c))
{
x=x*10+(c^48);
c=getchar();
}
return x;
}

using std::set;
using std::vector;
using std::pair;

typedef long long LL;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int imax_n = 1e5 + 7;

struct node
{
int l,r;
mutable bool v;
node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const
{
return l < o.l;
}
};

set<node> s;

//split(pos)操作是指将原来含有pos位置的节点分成两部分：[l,pos−1]和[pos,r]
IT split(int pos)
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r;
bool V = it->v;
s.erase(it);
s.insert(node(L, pos-1, V));
return s.insert(node(pos, R, V)).first;
//这里利用了pair<iterator,bool> insert (const value_type& val)的返回值
}

//ass♂ign操作迅速减小set的规模
void assign_val(int l, int r, bool val)
{
IT itr = split(r+1), itl = split(l);
s.erase(itl, itr);
//void erase (iterator first, iterator last)可删除[first,last)区间
s.insert(node(l, r, val));
}

void rev(int l, int r)
{
IT itr = split(r+1), itl = split(l);
for(; itl != itr; ++itl)
{
itl->v ^= 1;
}
}

int sum(int l, int r)
{
IT itr = split(r+1),itl = split(l);
int res = 0;
for (; itl != itr; ++itl)
res += itl->v ? itl->r - itl->l + 1 : 0;
return res;
}

int conti(int l,int r)
{
int res=0,temp=0;
IT itr = split(r+1),itl = split(l);
for(; itl != itr; ++itl)
{
if(itl->v == false)
{
res = std::max(res, temp);
temp=0;
}
else
{
temp += itl->r - itl->l + 1;
}
}
return std::max(res, temp);
}

LL a[imax_n];

int main()
{
for (int i=0; i<n; ++i)
{
}
s.insert(node(n, n, 0));
int op, a, b;
for (int i =1; i <= m; ++i)
{
if(op == 0)
{
assign_val(a, b, 0);
}
else if(op == 1)
{
assign_val(a, b, 1);
}
else if(op == 2)
{
rev(a, b);
}
else if(op == 3)
{
printf("%d\n",sum(a, b));
}
else
{
printf("%d\n",conti(a,b));
}
}
return 0;
}
• star
首页