QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#396823#5425. Proposition CompositionmarherRE 0ms24160kbC++174.2kb2024-04-23 11:14:522024-04-23 11:14:53

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 11:14:53]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:24160kb
  • [2024-04-23 11:14:52]
  • 提交

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

result: