首页 > 代码库 > POJ 2828Buy Tickets

POJ 2828Buy Tickets

2024-07-15 06:04:58   225人阅读

POJ 2828

题目大意是说有n个插入操作，每次把B插入到位置A，原来A以后的全部往后移动1,球最后的序列

tree里保存的应该是这整个区间还有多扫个位置可以插入数据，那么线段树里从后往前扫描依次插入数据

比如现在吧B插入到A位置，如果整个区间左侧还有<A个位置可以插入数据，那么就只能将其放到整个区间的右侧，递归下去就可以了

 1 void update(int k, int L, int R, int x) 2 { 3     if(L == R) { pre[k] = r; ans[L] = val; return ; } 4  5     int mid = (L+R)>>1; 6  7     if(x <= pre[k<<1]) update(lson, x);//左侧的多余x 8  9     else update(rson, x-pre[k<<1]);//否则往右10 11      pre[k] = pre[k<<1] + pre[k<<1|1];12 }

 

 1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype>10 #include <cstring>11 #include <cstdlib>12 #include <iostream>13 #include <algorithm>14 using namespace std;15 #define INF 1e916 #define inf (-((LL)1<<40))17 #define lson k<<1, L, mid18 #define rson k<<1|1, mid+1, R19 #define mem0(a) memset(a,0,sizeof(a))20 #define mem1(a) memset(a,-1,sizeof(a))21 #define mem(a, b) memset(a, b, sizeof(a))22 #define FOPENIN(IN) freopen(IN, "r", stdin)23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)24 template<class T> T CMP_MIN(T a, T b) { return a < b; }25 template<class T> T CMP_MAX(T a, T b) { return a > b; }26 template<class T> T MAX(T a, T b) { return a > b ? a : b; }27 template<class T> T MIN(T a, T b) { return a < b ? a : b; }28 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }29 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }30 31 typedef __int64 LL;32 //typedef long long LL;33 const int MAXN = 200005;34 const int MAXM = 100005;35 const double eps = 1e-10;36 const LL MOD = 1000000007;37 38 int N, pre[MAXN<<2];39 int id[MAXN], num[MAXN], ans[MAXN];40 int r, val;41 42 int buildTree(int k, int L, int R)43 {44     if(L == R) return pre[k] = 1;45     int mid = (L+R)>>1;46     return pre[k] = buildTree(lson) + buildTree(rson);47 }48 49 void update(int k, int L, int R, int x)50 {51     if(L == R) { pre[k] = r; ans[L] = val; return ; }52 53     int mid = (L+R)>>1;54 55     if(x <= pre[k<<1]) update(lson, x);56 57     else update(rson, x-pre[k<<1]);58 59      pre[k] = pre[k<<1] + pre[k<<1|1];60 }61 62 int main()63 {64     while(~scanf("%d", &N))65     {66         buildTree(1, 1, N);67         for(int l=1;l<=N;l++)68             scanf("%d %d", &id[l], &num[l]);69         r = 0;70         for(int i=N;i>0;i--)71         {72             val = num[i];73             update(1, 1, N, id[i] + 1);74         }75         for(int i=1;i<=N;i++) printf("%d%c", ans[i], i==N?‘\n‘:‘ ‘);76     }77     return 0;78 }

 


联系
我们