【DS】河南省第十三届ICPC大学生程序设计竞赛 J-甜甜圈

旧城等待， 2024-03-23 07:02 52阅读 0赞

**明天就要省赛了，感觉已经寄了捏**

[J-甜甜圈\_河南省第十三届ICPC大学生程序设计竞赛（重现赛） (nowcoder.com)][J-_ICPC_ _nowcoder.com]

题意：

![5450afad88d64bb19c11c4274c9bac53.png][]

思路：

直接模拟复杂度太高，因此考虑用DS优化

我们考虑用树状数组维护

在用线段树和树状数组之前，先去考虑好我们要维护的是哪个序列，我们需要维护的是序列的什么值

对于这道题，首先需要构造序列

因为他有两根，因此考虑把两根棒合并成一根，然后维护这一根就行

那就是把这两根棒头对头放着就行

每次操作我们找出最大值的位置，贡献加上该最大值头上有几个，然后把它删除

删除其实就是把1变成0

至于怎么去维护贡献，只需要记录上一次删除的位置即可

对于第一次删除，上一次删除的位置在n

这样就可以直接维护了，这题用线段树和也可以做！

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define low(x) ((x)&(-x))
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    struct ty{
    	int x,y;
    	bool operator<(const ty&a)const{
    		return a.y<y;
    	}
    }a[mxn];
    int n,m;
    int bitree[mxe<<2];
    void init(){
    	for(int i=0;i<=n+m;i++) bitree[i]=0;
    }
    int sum(int x){
    	int res=0;
        for(int i=x;i;i-=low(i)) res+=bitree[i];
        return res;
    }
    void insert(int pos,int x){
    	for(int i=pos;i<=n+m;i+=low(i)) bitree[i]+=x;
    }
    void solve(){
    	cin>>n>>m;
    	for(int i=n;i>=1;i--){
    		insert(i,1);
    		cin>>a[i].y;
    		a[i].x=i;
    	}
    	for(int i=n+1;i<=n+m;i++){
    		insert(i,1);
    		cin>>a[i].y;
    		a[i].x=i;
    	}
    	a[0].x=n;
    	sort(a+1,a+1+n+m);
    	int ans=0;
    	for(int i=1;i<=n+m;i++){
    		insert(a[i].x,-1);
    		//cout<<sum(a[i].x)<<'\n';
    		ans+=abs(sum(a[i].x)-sum(a[i-1].x));
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define low(x) ((x)&(-x))
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    struct ty{
    	int x,y;
    	bool operator<(const ty&a)const{
    		return a.y<y;
    	}
    }a[mxn];
    int n,m;
    int bitree[mxe<<2];
    void init(){
    	for(int i=0;i<=n+m;i++) bitree[i]=0;
    }
    int sum(int x){
    	int res=0;
        for(int i=x;i;i-=low(i)) res+=bitree[i];
        return res;
    }
    void insert(int pos,int x){
    	for(int i=pos;i<=n+m;i+=low(i)) bitree[i]+=x;
    }
    void solve(){
    	cin>>n>>m;
    	for(int i=n;i>=1;i--){
    		insert(i,1);
    		cin>>a[i].y;
    		a[i].x=i;
    	}
    	for(int i=n+1;i<=n+m;i++){
    		insert(i,1);
    		cin>>a[i].y;
    		a[i].x=i;
    	}
    	a[0].x=n;
    	sort(a+1,a+1+n+m);
    	int ans=0;
    	for(int i=1;i<=n+m;i++){
    		insert(a[i].x,-1);
    		//cout<<sum(a[i].x)<<'\n';
    		ans+=abs(sum(a[i].x)-sum(a[i-1].x));
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[J-_ICPC_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/17148/J
[5450afad88d64bb19c11c4274c9bac53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/413192d0fa2a432db30dc13bd7f58f9f.png