POJ2828 Buy Ticket

傳送門

題目大意：給一段空序列，每次向序列中某一個位置插入一個數，插入的位置后面所有數相應后移。

這個題比較令人頭疼的是后移操作，我們不可能大面積后移。那怎么辦呢？后面的人對前面有影響，那我們能不能通過離線方法，使得它變成沒有影響的狀態？

可以的。我們可以把輸入離線，然后倒著插入。這樣的話，這個數的pos在哪，他應該對應插入在第pos個空格的位置。注意本題序號從0開始，要加一。

這樣就豁然開朗啦！！真是神奇的操作！

看一下代碼。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<utility>
#include<map>
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define sc second
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')
using namespace std;
typedef long long ll;
const int M = 200005;
const int N = 10000005;int read()
{int ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >='0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op;
}struct node
{int id,val;
}q[M];int n,sum[M<<2],a[M];void clear()
{memset(q,0,sizeof(q));memset(sum,0,sizeof(sum));
}void build(int p,int l,int r)
{if(l == r){sum[p] = 1;return;}int mid = (l+r) >> 1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);sum[p] = sum[p<<1] + sum[p<<1|1];
}void modify(int p,int l,int r,int pos,int val)
{if(l == r){a[l] = val,sum[p]--;return;}int mid = (l+r) >> 1;if(sum[p<<1] >= pos) modify(p<<1,l,mid,pos,val);else modify(p<<1|1,mid+1,r,pos-sum[p<<1],val);sum[p] = sum[p<<1] + sum[p<<1|1];
}int main()
{while(scanf("%d",&n) != EOF){build(1,1,n);rep(i,1,n) q[i].id = read() + 1,q[i].val = read();per(i,n,1) modify(1,1,n,q[i].id,q[i].val);rep(i,1,n) printf("%d ",a[i]);enter;}return 0;
}

?