珂朵莉树求助
查看原帖
珂朵莉树求助
428690
Astatinear楼主2022/1/8 17:30

Sort 操作莫名 RE,tree.erase那里不知道为啥RE

#include<bits/stdc++.h>
using namespace std;
#define It set<odt>::iterator
#define ll long long
struct odt
{
	ll l,r;
	mutable ll val;
	bool operator <(const odt &n)const
	{
		return l<n.l;
	}
	odt(ll a,ll b,ll c)
	{
		l=a,r=b,val=c;
	}
	odt(ll a)
	{
		l=a;
	}
};
set<odt> tree;
It split(ll x)
{
	It it=tree.lower_bound(x);
	if(it!=tree.end()&&it->l==x)
	return it;
	it--;
	ll l=it->l,r=it->r,val=it->val;
	tree.erase(it);
	tree.insert(odt(l,x-1,val));
	return tree.insert(odt(x,r,val)).first;
}
void assign(ll l,ll r,ll val)
{
	It it2=split(r+1),it1=split(l);
	tree.erase(it1,it2);
	tree.insert(odt(l,r,val));
}
ll time_k(ll l,ll r,ll k)
{
	It it2=split(r+1),it1=split(l);
	ll ans=0;
	for(It it=it1;it!=it2;it++)
	{
		if(it->val==k)
		ans+=it->r-it->l+1;
	}
	return ans;
}
void Sort(ll l,ll r)
{
	It it2=split(r+1),it1=split(l);
	ll k=l;
	int bucket[125];
	memset(bucket,0,sizeof(bucket));
	for(;it1!=it2;it1++)
	{
		bucket[it1->val]+=it1->r-it1->l+1;
		tree.erase(it1);
//		cout<<it->l<<" "<<it->r<<endl;
	}
	for(int i='A';i<='Z';++i)
	{
		tree.insert(odt(k,k+bucket[i],i));
		k+=bucket[i];
	}
}
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	scanf("\n");
	for(int i=1;i<=n;++i)
	{
		char a=getchar();
		tree.insert(odt(i,i,a));
	}
	for(int i=1;i<=m;++i)
	{
		int op,x,y;
		char k;
		scanf("%d%d%d",&op,&x,&y);
		if(op<=2)
		{
			getchar();
			k=getchar();
		}
		if(op==1)
		{
			printf("%lld\n",time_k(x,y,k));
		}
		else if(op==2)
		{
			assign(x,y,k);
		}
		else
		{
			Sort(x,y);
		}
	}
	return 0;
}
2022/1/8 17:30
加载中...