題意不說了。思路是將人倒敘插入，線段樹各個區間的值代表前面有多少個空位。
#include #include #include #include #include #include #include #include #include #include #define LL __int64 using namespace std; const int maxn=200005; int sum[maxn*4]; int num[maxn*4]; int p[maxn],v[maxn]; void build(int o,int L,int R) //建樹過程 { if(L==R) { sum[o]=1; //初始都為1 return; } int M=(L+R)>>1; build(o*2,L,M); //左子樹 build(o*2+1,M+1,R); //右子樹 sum[o]=sum[o*2+1]+sum[o*2]; //當前區間的和為左右子樹的和 } void update(int o,int p,int w,int L,int R) { if(L==R && sum[o]==1) //1表示這個位置沒有人 { sum[o]--; num[L]=w; return; } int M=(L+R)>>1; if(p>sum[o*2]) update(o*2+1,p-sum[o*2],w,M+1,R); //注意這裡p要減去左子樹的值 else update(o*2,p,w,L,M); sum[o]=sum[o*2]+sum[o*2+1]; } int main() { int n; while(scanf("%d",&n)!=EOF) { build(1,1,n); for(int i=0;i=0;i--) { update(1,p[i],v[i],1,n); } for(int i=1;i<=n;i++) { printf("%d",num[i]); if(i==n) printf("\n"); else printf(" "); } } return 0; }
單看這文章的標題，你可能會覺得好像沒什麼意思。你先別下這個
Qt Creator下應用CMake項目調試mex文件，cm
chatofPomelo game-server解析 c
chrome插件開發-----------將網址轉化成二維碼
Problem Description Alice and
題目 Given n non-negative i
