QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#396823 | #5425. Proposition Composition | marher | RE | 0ms | 24160kb | C++17 | 4.2kb | 2024-04-23 11:14:52 | 2024-04-23 11:14:53 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=6e5+50,inf=1e9;
vector<int>p;
struct tree
{
int ty,w[N],a[N];
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
int chk(int a,int b)
{
return ty?min(a,b):max(a,b);
}
void build(int x,int l,int r)
{
if(l==r)
{
if(a[l])w[x]=a[l];
else w[x]=ty?inf:0;
return;
}
build(ls,l,mid);build(rs,mid+1,r);
w[x]=chk(w[ls],w[rs]);
}
void find(int x,int l,int r,int L,int R,int l2,int r2)
{
if(L<=l&&R>=r)
{
if(w[x]<l2||w[x]>r2)return;
if(l==r)p.push_back(w[x]);
else find(ls,l,mid,L,R,l2,r2),find(rs,mid+1,r,L,R,l2,r2);
return;
}
if(L<=mid)find(ls,l,mid,L,R,l2,r2);
if(R>mid)find(rs,mid+1,r,L,R,l2,r2);
}
void insert(int x,int l,int r,int d,int rw)
{
if(l==r)return w[x]=(rw?rw:ty?inf:0),void();
if(d<=mid)insert(ls,l,mid,d,rw);
else insert(rs,mid+1,r,d,rw);
w[x]=chk(w[ls],w[rs]);
}
}pre,las;
int n,m,mi[N],la[N],tot,val[N],ch[N][2],fa[N],rd[N],T,sum[N],v[N],c0,c1;ll ans;
ll C(int n)
{
return 1ll*n*(n-1)/2;
}
void clear()
{
tot=ans=c0=c1=0;
for(int i=1;i<=n;i++)pre.a[i]=las.a[i]=0;
}
int mkn(int w)
{
val[++tot]=w;rd[tot]=rand();ch[tot][0]=ch[tot][1]=fa[tot]=sum[tot]=v[tot]=0;
return tot;
}
int findroot(int x)
{
return fa[x]?findroot(fa[x]):x;
}
void build(int x,int l,int r)
{
mi[x]=la[x]=0;
if(l==r)return;
build(ls,l,mid);build(rs,mid+1,r);
}
void down(int x)
{
int&w=la[x];
la[ls]+=w;mi[ls]+=w;
la[rs]+=w;mi[rs]+=w;
w=0;
}
void dfs(int x,int l,int r)
{
if(mi[x]>2)return;
if(l==r)
{
if(mi[x]==1)
{
c0--,c1++;
v[l]=1;int ro=l;
while(l)++sum[l],ro=l,l=fa[l];
ans-=C(sum[ro]-1)-C(sum[ro]);
}
if(mi[x]==2)c1--;
return;
}
down(x);dfs(ls,l,mid);dfs(rs,mid+1,r);
}
void insert(int x,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
mi[x]++;la[x]++;
return dfs(x,l,r);
}
down(x);
if(L<=mid)insert(ls,l,mid,L,R);
if(R>mid)insert(rs,mid+1,r,L,R);
mi[x]=min(mi[ls],mi[rs]);
}
void solve(ll tot)
{
cout<<c0*(tot-1)-C(c0)+c1+ans<<'\n';
}
void up(int x)
{
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x];
}
int merge(int a,int b,int f)
{
if(a+b==0)return 0;
if(!a||!b){fa[a+b]=f;return a+b;}
if(rd[a]<rd[b])
{
ch[a][1]=merge(ch[a][1],b,a);
fa[a]=f;up(a);return a;
}
ch[b][0]=merge(a,ch[b][0],b);
fa[b]=f;up(b);return b;
}
void split(int x,int k,int&a,int&b,int Fa,int Fb)
{
if(!x)return a=b=0,void();
if(x<=k)a=x,fa[x]=Fa,split(ch[x][1],k,ch[x][1],b,x,Fb);
else b=x,fa[x]=Fb,split(ch[x][0],k,a,ch[x][0],Fa,x);
up(x);
}
int findl(int x)
{
return ch[x][0]?findl(ch[x][0]):x;
}
int findr(int x)
{
return ch[x][1]?findr(ch[x][1]):x;
}
void solve(int x,int l,int r)
{
int ro=findroot(x);
ans-=C(sum[ro]);
int a=0,b=0,c=0;
split(ro,l-1,a,b,0,0);split(b,r,b,c,0,0);
int ra=findr(a),lb=findl(b),rb=findr(b),lc=findl(c);
if(ra)pre.insert(1,1,n,ra,lc),las.insert(1,1,n,lb,0);
if(lc)las.insert(1,1,n,lc,ra),pre.insert(1,1,n,rb,0);
a=merge(a,c,0);
ans+=C(sum[a])+C(sum[b]);
}
void sol()
{
cin>>n>>m;n--;
c0=n,c1=0;pre.ty=0,las.ty=1;
for(int i=1;i<n;i++)las.a[i+1]=i,pre.a[i]=i+1;
int ro=mkn(1);
for(int i=2;i<=n;i++)ro=merge(ro,mkn(i),0);
build(1,1,n);las.build(1,1,n);pre.build(1,1,n);
for(int i=1;i<=m;i++)
{
int l,r;cin>>l>>r;
if(l==r){solve(n+i);continue;}
if(l>r)swap(l,r);r--;
insert(1,1,n,l,r);
vector<int>().swap(p);
las.find(1,1,n,l,r,1,l-1);
for(auto x:p)solve(x,l,r);
vector<int>().swap(p);
pre.find(1,1,n,l,r,r+1,n);
for(auto x:p)solve(x,l,r);
solve(n+i);
}
}
main()
{
cin>>T;T=min(T,22);
while(T--)sol(),clear();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 24160kb
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
Runtime Error
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...
output:
45 36 36 36 36 36 36 36 36 45 36 28 21 21 15 10 10 10 6 36 44 50 57 28 21 15 28 28 21 21 15 15 10 3 1 1 3 3 3 3 1 1 1 0 0 45 21 3 1 1 1 1 1 1 1 3 1 1 1 1 1 45 36 36 36 36 36 36 36 3 3 1 0 0 0 0 0 0 3 1 0 0 15 10 10