3192: [JLOI2013]删除物品
Time Limit: 10 Sec
Memory Limit: 128 MB
Submit: 977
Solved: 558
[
Submit][
Status][
Discuss]
Description
箱子再分配问题需要解决如下问题：
（1）一共有N个物品，堆成M堆。
（2）所有物品都是一样的，但是它们有不同的优先级。
（3）你只能够移动某堆中位于顶端的物品。
（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。
（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。
（6）只是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：
不会有两个物品有着相同的优先级，且M=2
Input
第一行是包含两个整数N1,N2分别表示两堆物品的个数。
接下来有N1行整数按照从顶到底的顺序分别给出了第一堆物品中的优先级，数字越大，优先级越高。
再接下来的N2行按照同样的格式给出了第二堆物品的优先级。
Output
对于每个数据，请输出一个整数，即最小移动步数。
Sample Input
3 3 1 4 5 2 7 3
Sample Output
6
HINT
1<=N1+N2<=100000
Source
[
Submit][
Status][
Discuss]
题目扯了很长，但是有用的只有那几句话。。。
根据规则，每次能删除的物品一定是当前局面权值最大的
那么找到那个物品，把在它上面的物品全部搬到另一个堆就行了
移动方法也是唯一的。。。。。
这等于是删除序列，合并序列，翻转序列同时存在。。。。
用splay可以维护所有操作~(我真的这么写了。。)
然后一搜题解。。。。树状数组就行了。。。。。。。。。。。
把两个堆堆顶对着堆顶摆好。。。剩下就。。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn = 1E5 + 10;
const int INF = ~0U>>1;
typedef long long LL;
int n1,n2,rt1,rt2,cnt,tp,now,fa[maxn],A[maxn],B[maxn],Max[maxn]
,key[maxn],rev[maxn],ch[maxn][2],stk[maxn],siz[maxn];
LL Ans;
void pushdown(int x)
{
if (rev[x])
{
for (int i = 0; i < 2; i++)
if (ch[x][i]) rev[ch[x][i]] ^= 1;
rev[x] = 0; swap(ch[x][0],ch[x][1]);
}
}
void maintain(int x)
{
Max[x] = key[x]; siz[x] = 1;
for (int i = 0; i < 2; i++)
if (ch[x][i]) Max[x] = max(Max[x],Max[ch[x][i]]),siz[x] += siz[ch[x][i]];
}
void rotate(int x)
{
int y = fa[x],z = fa[y];
int d = ch[y][0] == x ? 0 : 1;
ch[y][d] = ch[x][d^1]; fa[ch[y][d]] = y;
ch[x][d^1] = y; fa[y] = x; fa[x] = z;
maintain(y); maintain(x);
if (z) ch[z][ch[z][1] == y] = x;
}
void splay(int x,int &rt)
{
for (int z = x; z; z = fa[z]) stk[++tp] = z;
while (tp) pushdown(stk[tp--]);
for (int y = fa[x]; y; rotate(x),y = fa[x])
if (fa[y]) rotate((ch[y][0] == x) ^ (ch[fa[y]][0] == y) ? x : y);
rt = x;
}
int Search(int x,int k)
{
pushdown(x);
if (key[x] == k) {now += siz[ch[x][0]] + 1; return x;}
if (Max[ch[x][0]] == k) return Search(ch[x][0],k);
else {now += siz[ch[x][0]] + 1; return Search(ch[x][1],k);}
}
int Left(int x)
{
pushdown(x);
if (!ch[x][0]) return x;
return Left(ch[x][0]);
}
void Merge(int &rt,int g)
{
int y = Left(rt); splay(y,rt);
rev[g] ^= 1; pushdown(g);
ch[y][0] = g; fa[g] = y; maintain(y);
}
int Build_A(int l,int r)
{
if (l > r) return 0;
int mid = l + r >> 1,ret = ++cnt; key[ret] = A[mid];
ch[ret][0] = Build_A(l,mid-1); if (ch[ret][0]) fa[ch[ret][0]] = ret;
ch[ret][1] = Build_A(mid+1,r); if (ch[ret][1]) fa[ch[ret][1]] = ret;
maintain(ret); return ret;
}
int Build_B(int l,int r)
{
if (l > r) return 0;
int mid = l + r >> 1,ret = ++cnt; key[ret] = B[mid];
ch[ret][0] = Build_B(l,mid-1); if (ch[ret][0]) fa[ch[ret][0]] = ret;
ch[ret][1] = Build_B(mid+1,r); if (ch[ret][1]) fa[ch[ret][1]] = ret;
maintain(ret); return ret;
}
int getint()
{
char ch = getchar(); int ret = 0,a = 1;
while (ch < '0' || '9' < ch)
{
if (ch == '-') a = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9')
ret = ret * 10 + ch - '0',ch = getchar();
return ret * a;
}
int main()
{
#ifdef DMC
freopen("DMC.txt","r",stdin);
#endif
n1 = getint(); n2 = getint();
for (int i = 1; i <= n1; i++) A[i] = getint();
for (int i = 1; i <= n2; i++) B[i] = getint();
A[++n1] = B[++n2] = -INF;
rt1 = Build_A(1,n1); rt2 = Build_B(1,n2);
for (int i = 1; i <= n1 + n2 - 2; i++)
{
pushdown(rt1); pushdown(rt2);
if (Max[rt1] > Max[rt2])
{
int g = Search(rt1,Max[rt1]);
Ans += 1LL * (now - 1); now = 0;
splay(g,rt1); rt1 = ch[g][1]; fa[rt1] = 0;
if (ch[g][0]) Merge(rt2,ch[g][0]);
}
else
{
int g = Search(rt2,Max[rt2]);
Ans += 1LL * (now - 1); now = 0;
splay(g,rt2); rt2 = ch[g][1]; fa[rt2] = 0;
if (ch[g][0]) Merge(rt1,ch[g][0]);
}
}
cout << Ans << endl;
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-37782.html
