社区讨论

萌新求教,刚学线段树,调不出错误来了,求大佬指教

P4511[CTSC2015] 日程管理参与者 18已保存回复 25

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
25 条
当前快照
1 份
快照标识符
@mi6tuhq3
此快照首次捕获于
2025/11/20 10:43
4 个月前
此快照最后确认于
2025/11/20 15:04
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
#include <set>
#include <cctype>

using namespace std;

struct SegTree1
{
	struct node
	{
		int left,right,value,tag;
	}t[300050<<2];
	
	void Push_Up(int id)
	{
		t[id].value=min(t[id*2].value,t[id*2+1].value);
	}
	
	void Push_Down(int id)
	{
		t[id*2].value+=t[id].tag;
		t[id*2+1].value+=t[id].tag;
		t[id*2].tag+=t[id].tag;
		t[id*2+1].tag+=t[id].tag;
		t[id].tag=0;
	}
	
	void Build(int id,int left,int right)
	{
		t[id].left=left;
		t[id].right=right;
		t[id].value=left;
		t[id].tag=0;
		if (left==right)
			return;
		int mid=(left+right)/2;
		Build(id*2,left,mid);
		Build(id*2+1,mid+1,right);
	}
	
	void Change(int id,int left,int right,int value)
	{
		if (t[id].right<left && t[id].left>right)
			return;
		if (left<=t[id].left && t[id].right<=right)
		{
			t[id].tag+=value;
			t[id].value+=value;
		}
		Push_Down(id);
		Change(id*2,left,right,value);
		Change(id*2+1,left,right,value);
		Push_Up(id);
	}
	
	int QueryLeft(int id,int left,int right,int pos)
	{
		if (t[id].value)
			return 0;
		if (left==right)
			return left;
		Push_Down(id);
		int mid=(left+right)/2;
		if (pos<=mid)
		{
			int tmp=QueryLeft(id*2,left,mid,pos);
			if (tmp)
				return tmp;
		}
		return QueryLeft(id*2+1,mid+1,right,pos);
	}
	
	int QueryRight(int id,int left,int right)
	{
		if (t[id].value)
			return 0;
		if (left==right)
			return left;
		Push_Down(id);
		int mid=(left+right)/2;
		int tmp=QueryRight(id*2+1,mid+1,right);
		if (tmp)
			return tmp;
		else return QueryRight(id*2,left,mid);
	}
}t1;

struct node
{
	int left,right,value,pos;
}t[300050<<2];

struct SegTree2
{
	multiset <int> q[300050];
	
	const int INF=1<<30;
	
	node Merge(node a,node b)
	{
		if (a.value<b.value)
			return a;
		return b;
	}
	
	void Build(int id,int left,int right)
	{
		t[id].left=left;
		t[id].right=right;
		if (left==right)
		{
			t[id].value=INF;
			t[id].pos=left;
			q[left].insert(INF);
			return;
		}
		int mid=(left+right)/2;
		Build(id*2,left,mid);
		Build(id*2+1,mid+1,right);
		t[id]=Merge(t[id*2],t[id*2+1]);
	}
	
	void Change(int id,int left,int right,int fafa,int value)
	{
		if (left==right)
		{
			t[id].value=min(t[id].value,value);
			q[left].insert(value);
			return;
		}
		int mid=(left+right)/2;
		if (fafa<=mid)
			Change(id*2,left,mid,fafa,value);
		else Change(id*2+1,mid+1,right,fafa,value);
		t[id]=Merge(t[id*2],t[id*2+1]);
	}
	
	bool Delete(int id,int left,int right,int fafa,int value)
	{
		if (t[id].value>value)
			return false;
		if (left==right)
		{
			q[left].erase(q[left].find(value));
			t[id].value=*q[left].begin();
			return true;
		}
		int mid=(left+right)/2;
		int res;
		if (fafa<=mid)
			res=Delete(id*2,left,mid,fafa,value);
		else res=Delete(id*2,mid+1,right,fafa,value);
		t[id]=Merge(t[id*2],t[id*2+1]);
		return res;
	}
	
	node Query(int id,int left,int right,int qleft,int qright)
	{
		if (qleft<=left && right<=qright)
			return t[id];
		int mid=(left+right)/2;
		if (qright<=mid)
			return Query(id*2,left,mid,qleft,qright);
		if (qleft>mid)
			return Query(id*2+1,mid+1,right,qleft,qright);
		return Merge(Query(id*2,left,mid,qleft,qright),Query(id*2+1,mid+1,right,qleft,qright));
	}
	
}t2,t3;

int n,m; 

int read()
{
	int x=0;char ch=getchar();
	while (!isdigit(ch))ch=getchar();
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x;
}

long long ans=0;

int main()
{
	n=read();
	m=read();
	t1.Build(1,1,n);
	t2.Build(1,1,n);
	t3.Build(1,1,n);
	while (m--)
	{
		string s;
		cin >> s;
		int ti=read(),p=read();
		if (s=="ADD")
		{
			int pos=t1.QueryLeft(1,1,n,ti);
			if (pos==0)
			{
				ans+=p;
				t2.Change(1,1,n,ti,p);
				t1.Change(1,ti,n,-1);
			}
			else
			{
				node tmp=t2.Query(1,1,n,1,pos);
				if (p>tmp.value)
				{
					ans+=p-tmp.value;
					t2.Delete(1,1,n,tmp.pos,tmp.value);
					t1.Change(1,tmp.pos,n,1);
					t3.Change(1,1,n,tmp.pos,-tmp.value);
					t2.Change(1,1,n,ti,p);
					t1.Change(1,ti,n,-1);
				}
				else
					t3.Change(1,1,n,ti,p);
			}
		}
		else
		{
			if(!t3.Delete(1,1,n,ti,-p))
			{
		        ans-=p;
		        t2.Delete(1,1,n,ti,p);
		        t1.Change(1,ti,n,1);
		        int pos=t1.QueryRight(1,1,n);
		        node x=t3.Query(1,1,n,pos+1,n);
		        if(x.value<=0)
		        {
		            ans-=x.value;
		            t3.Delete(1,1,n,x.pos,x.value);
		            t2.Change(1,1,n,x.pos,-x.value);
		            t1.Change(1,x.pos,n,-1);
		        }
		    }
		}
		printf("%lld\n",ans);
	}
	return 0;
}

回复

25 条回复,欢迎继续交流。

正在加载回复...