南浔区住房和城乡建设网站,wordpress 下载文件,网站开发维护人员,网站关键词数量传送门 题目大意#xff1a;给一段空序列#xff0c;每次向序列中某一个位置插入一个数#xff0c;插入的位置后面所有数相应后移。 这个题比较令人头疼的是后移操作#xff0c;我们不可能大面积后移。那怎么办呢#xff1f;后面的人对前面有影响#xff0c;那我们能不能…传送门 题目大意给一段空序列每次向序列中某一个位置插入一个数插入的位置后面所有数相应后移。 这个题比较令人头疼的是后移操作我们不可能大面积后移。那怎么办呢后面的人对前面有影响那我们能不能通过离线方法使得它变成没有影响的状态 可以的。我们可以把输入离线然后倒着插入。这样的话这个数的pos在哪他应该对应插入在第pos个空格的位置。注意本题序号从0开始要加一。 这样就豁然开朗啦真是神奇的操作 看一下代码。 #includeiostream
#includecstdio
#includecmath
#includealgorithm
#includequeue
#includecstring
#includeutility
#includemap
#define pr pairint,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[M2],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 (lr) 1;build(p1,l,mid),build(p1|1,mid1,r);sum[p] sum[p1] sum[p1|1];
}void modify(int p,int l,int r,int pos,int val)
{if(l r){a[l] val,sum[p]--;return;}int mid (lr) 1;if(sum[p1] pos) modify(p1,l,mid,pos,val);else modify(p1|1,mid1,r,pos-sum[p1],val);sum[p] sum[p1] sum[p1|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;
} 转载于:https://www.cnblogs.com/captain1/p/9795207.html
