【BZOJ 3192】【JLOI 2013】アイテムシミュレーションの削除
#include <stdio.h>
int main()
{
puts(" ");
puts("http://blog.csdn.net/vmurder/article/details/43064295");
}問題:
コード内のinitは現在の左スタックトップ番号です.
各アイテムにマッピングしてソートし、暴力を最大から最小にスキャンします.
2つのシーケンス番号の間に存在するアイテムの数(ツリー配列、セグメントツリーで)を加算するたびに、アイテムを削除してinitを変更します.
どうせ水が爆発するまで、むやみにやればいい.
コード:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
using namespace std;
struct LSH
{
int x,id;
bool operator < (const LSH &a)const{return x<a.x;}
LSH(int _x=0,int _id=0):x(_x),id(_id){}
}seq[N];
int n,m,init;
int fw[N];
inline void add(int x,int w){for(;x<=n;x+=(x&-x))fw[x]+=w;}
inline int query(int x){int ans=0;for(;x;x-=(x&-x))ans+=fw[x];return ans;}
int main()
{
int i,j,k;
int a,b,c;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a);
seq[i]=LSH(-a,n-i+1);
}
init=n;
for(i=1;i<=m;i++)
{
scanf("%d",&a);
seq[i+n]=LSH(-a,i+n);
}
n+=m;
sort(seq+1,seq+n+1);
//
// init ，
for(i=1;i<=n;i++)add(i,1);
long long ans=0;
for(i=1;i<=n;i++)
{
int d=seq[i].id;
if(init<=d)
{
int t=query(d-1)-query(init);
if(t>0)ans+=t;
add(d,-1),init=d;
}
else {
int t=query(init)-query(d);
if(t>0)ans+=t;
add(d,-1),init=d;
}
}
cout<<ans<<endl;
return 0;
}