首页 > 代码库 > POJ 2828Buy Tickets
POJ 2828Buy Tickets
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。