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

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

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

题意：

思路：

直接模拟复杂度太高，因此考虑用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;
}