1 条题解

  • 0
    @ 2021-6-15 14:10:52

    C++ :

    
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define ls ch[p][0]
    #define rs ch[p][1]
    #define PI pair<int,int>
    #define mp(a,b) make_pair(a,b)
    #define fi first
    #define se second
    const int maxn=100010;
    using namespace std;
    typedef long long ll;
    int n,m,P;PI poi[maxn];ll res;
    
    struct Treap{
    	int ch[maxn][2],add[maxn],size[maxn],h[maxn],root;
    	ll ans[maxn];
    	void inc(int p,int v){if (p) h[p]+=v,add[p]+=v;}
    	void down(int p){
    		if (add[p]){
    			if (ls) inc(ls,add[p]);
    			if (rs) inc(rs,add[p]);
    			add[p]=0;
    		}
    	}
    	void update(int p){
    		size[p]=1,ans[p]=0;
    		if (ls) size[p]+=size[ls],ans[p]+=ans[ls]+1ll*(h[ls]-h[p])*size[ls]*(size[ls]+1)/2;
    		if (rs) size[p]+=size[rs],ans[p]+=ans[rs]+1ll*(h[rs]-h[p])*size[rs]*(size[rs]+1)/2;
    	}
    	int merge(int a,int b){
    		if (!a){update(b);return b;}
    		if (!b){update(a);return a;}
    		down(a),down(b);
    		if (h[a]<h[b]){ch[a][1]=merge(ch[a][1],b),update(a);return a;}
    		else{ch[b][0]=merge(a,ch[b][0]),update(b);return b;}
    	}
    	PI split(int p,int k){
    		if (!p) return mp(0,0);
    		down(p);
    		if (size[ls]+1<=k){
    			PI tmp=split(rs,k-size[ls]-1);
    			rs=tmp.first,update(p);
    			return mp(p,tmp.second);
    		}
    		else{
    			PI tmp=split(ls,k);
    			ls=tmp.second,update(p);
    			return mp(tmp.first,p);
    		}
    	}
    	ll query(){
    		down(root);
    		return ans[root]+1ll*h[root]*size[root]*(size[root]+1)/2;
    	}
    	void work(){
    		for (int i=1,j=1;i<=n;i++){
    			inc(root,1);
    			for (;poi[j].fi==i;j++){
    				PI tmp1=split(root,poi[j].se-1),tmp2=split(tmp1.se,1);
    				h[tmp2.fi]=0;
    				root=merge(merge(tmp1.fi,tmp2.fi),tmp2.se);
    			}
    			res-=query();
    		}
    		printf("%lld\n",res);
    	}
    }T;
    
    int main(){
    	scanf("%d%d%d",&n,&m,&P);
    	for (int i=1;i<=P;i++) scanf("%d%d",&poi[i].fi,&poi[i].se);
    	sort(poi+1,poi+1+P);
    	for (int i=1;i<=m;i++) T.root=T.merge(T.root,i);
    	res=1ll*n*(n+1)/2*m*(m+1)/2;T.work();
    	return 0;
    }
    
    • 1

    信息

    ID
    975
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者