初学ODT,求助CE
查看原帖
初学ODT,求助CE
516468
_Give_up_楼主2022/10/21 20:50
#include<bits/stdc++.h>

using namespace std;

int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
	{
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
	{
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

struct ODT
{
	int l,r,v;
	ODT (int il,int ir,int iv) : l(il),r(ir),v(iv) {}
	bool operator <(ODT o)
	{
		return l<o.l;
	}
};

set <ODT> odt;
int n,ans=0;

set <ODT>::iterator split(int x)
{
	if (x>n) return odt.end();
	auto it = odt.upper_bound(ODT{x,0,0});
	if (it->l==x) return it;
	int l = it->l, r = it->r, v = it->v;
	odt.erase(it);
	odt.insert(ODT(l,x-1,v));
	return odt.insert(ODT(x,r,v)).first;
}

void assign(int l,int r,int v)
{
	auto itr = split(r+1),itl = split(l);
	for (set <ODT>::iterator it=itl;it!=itr;it++)
        ans -= (it->v)*(it->r-it->l+1);
	odt.erase(itl,itr);
	odt.insert(ODT(l,r,v));
	ans += v*(r-l+1);
}

int main()
{
	n=read();
	int q=read();
	odt.insert(ODT(1,n,1));
	while(q--)
	{
		int l=read(),r=read(),k=read();
        assign(l,r,!k);
        printf("%d",n-ans);
	}
	return 0; 
}
2022/10/21 20:50
加载中...