QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556690 | #5425. Proposition Composition | Wuyanru | ML | 2ms | 14024kb | C++14 | 3.4kb | 2024-09-10 20:12:37 | 2024-09-10 20:12:37 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int L[5000001];
int R[5000001];
int ls[5000001];
int rs[5000001];
int fa[5000001];
int c[5000001];
set<int>S0,S1,nod;
ll ans;
int n,m,cnt;
inline void clear()
{
S0.clear(),S1.clear(),nod.clear();
}
inline void cover(int l,int r)
{
auto it=S1.lower_bound(l);
while(it!=S1.end()&&*it<r) S1.erase(it),it=S1.lower_bound(l);
it=S0.lower_bound(l);
while(it!=S0.end()&&*it<r) S1.insert(*it),S0.erase(it),it=S0.lower_bound(l);
}
inline void push_up(int p)
{
c[p]=c[ls[p]]+c[rs[p]];
L[p]=min(L[ls[p]],L[rs[p]]);
R[p]=max(R[ls[p]],R[rs[p]]);
if(ls[p]) fa[ls[p]]=p;
if(rs[p]) fa[rs[p]]=p;
}
inline ll run(int p)
{
return (ll)c[p]*(c[p]-1)/2;
}
void split(int p,int pl,int pr,int l,int r,int &x,int &y)
{
// printf("split %d %d %d %d %d\n",p,pl,pr,l,r);
if(!p){ x=y=0;return ;}
if(l<=L[p]&&R[p]<=r){ x=p,y=0;return ;}
if(R[p]<l||r<L[p]){ x=0,y=p;return ;}
int mid=(pl+pr)>>1;
int L1,R1,L2,R2;
split(ls[p],pl,mid,l,r,L1,L2);
split(rs[p],mid+1,pr,l,r,R1,R2);
if(!L1&&!R1){ x=0,y=p;return ;}
if(!L2&&!R2){ x=p,y=0;return ;}
x=p,ls[x]=L1,rs[x]=R1;
y=++cnt,ls[y]=L2,rs[y]=R2,fa[y]=0;
push_up(x),push_up(y);
}
inline bool check(int id)
{
if(id==1||id==n) return false;
if(nod.find(id)!=nod.end()) return false;
nod.insert(id);
return true;
}
inline int get(int u)
{
while(fa[u]) u=fa[u];
return u;
}
inline void edge()
{
// for(int i=1;i<=cnt;i++) printf("%d : c=%d ls=%d rs=%d fa=%d L=%d R=%d\n",i,c[i],ls[i],rs[i],fa[i],L[i],R[i]);
int u=read(),v=read();
if(u==v) return ;
if(u>v) swap(u,v);
cover(u,v);
if(check(u)){ int pu=get(u),x,y;ans-=run(pu);split(pu,1,n-1,u,v-1,x,y);ans+=run(x)+run(y);}
// for(int i=1;i<=cnt;i++) printf("%d : c=%d ls=%d rs=%d fa=%d L=%d R=%d\n",i,c[i],ls[i],rs[i],fa[i],L[i],R[i]);
if(check(v)){ int pv=get(v-1),x,y;ans-=run(pv);split(pv,1,n-1,u,v-1,x,y);ans+=run(x)+run(y);}
// for(int i=1;i<=cnt;i++) printf("%d : c=%d ls=%d rs=%d fa=%d L=%d R=%d\n",i,c[i],ls[i],rs[i],fa[i],L[i],R[i]);
}
int build(int pl,int pr)
{
if(pl==pr)
{
L[pl]=R[pl]=pl;c[pl]=1;
return pl;
}
int p=++cnt,mid=(pl+pr)>>1;fa[p]=0;
ls[p]=build(pl,mid);
rs[p]=build(mid+1,pr);
push_up(p);
return p;
}
inline void solve()
{
clear();
n=read(),m=read(),cnt=n-1;
for(int i=1;i<n;i++) S0.insert(i);
ans=run(build(1,n-1));
for(int i=1;i<=m;i++)
{
edge();
ll o=ans+(int)S1.size()+(ll)S0.size()*(n-1-S0.size()+i);
// printf("ans=%lld %lld %lld\n",ans,(ll)S0.size(),n-1-(ll)S0.size()+i);
printf("%lld\n",o);
}
}
int main()
{
int T=read();L[0]=0x3f3f3f3f,R[0]=0;
while(T--) solve();
return 0;
}
/*
1
4 2
2 4
2 4
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 14024kb
input:
3 4 3 2 4 4 2 3 3 7 3 3 4 1 2 1 7 6 4 1 3 4 6 2 5 3 4
output:
6 5 6 21 24 10 15 12 3 2
result:
ok 10 numbers
Test #2:
score: -100
Memory Limit Exceeded
input:
45540 10 9 10 1 1 10 10 1 1 10 1 10 10 1 1 10 3 3 10 1 10 4 1 2 1 10 3 4 1 10 7 6 7 1 5 6 1 7 6 6 7 1 6 7 9 7 3 3 7 7 5 4 1 1 9 1 9 1 6 5 8 7 1 8 4 4 5 6 1 1 1 8 6 6 4 5 3 3 3 2 3 1 3 3 3 9 3 1 3 3 2 2 3 3 3 1 2 2 1 1 2 3 3 1 10 1 2 1 7 1 1 7 3 8 1 3 1 3 3 3 1 3 2 2 1 3 1 3 3 3 3 6 3 1 1 3 1 3 1 3 1...