社区讨论
萌新求教,刚学线段树,调不出错误来了,求大佬指教
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 条回复,欢迎继续交流。
正在加载回复...