这题写不了ODT吗?还是说我的代码有问题
查看原帖
这题写不了ODT吗?还是说我的代码有问题
516468
_Give_up_楼主2023/2/5 14:58
#include<bits/stdc++.h>
#define IT set<ODT>::iterator

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;
	mutable int v;
	ODT(int L,int R=-1,int V=0): l(L),r(R),v(V) {}
	bool operator <(const ODT &o) const
	{
		return l<o.l;
	}
};

set <ODT> s;

IT split(int x)
{
	IT it = s.lower_bound(ODT(x));
	if (it!=s.end() && it->l==x) return it;
	--it;
	int L = it->l,R = it->r,V = it->v;
	s.erase(it);
	s.insert(ODT(L,x-1,V));
	return s.insert(ODT(x,R,V)).first;
}

void assign(int l,int r,int v)
{
	IT itr = split(r+1),itl = split(l);
	s.erase(itl,itr);
	s.insert(ODT(l,r,v));
}

int query(int l,int r)
{
	set <int> st;
	IT itr = split(r+1),itl = split(l);
	for (IT it=itl;it!=itr;it++)
		st.insert(it->v);
	return st.size();
}

int main()
{
	int n=read(),t=read(),q=read();
	s.insert(ODT(1,n,1));
	while(q--)
	{
		char opt;
		cin >> opt;
		if (opt=='C')
		{
			int l=read(),r=read(),c=read();
			assign(l,r,c);
		}
		else
		{
			int l=read(),r=read();
			cout << query(l,r) << endl;
		}
	}
	return 0; 
}

记录

2023/2/5 14:58
加载中...