免费制作贺卡的app,关键词排名优化江苏的团队,网站建设费可以抵扣进项税吗,如何替别人建网站挣钱P3992 [BJOI2017]开车
题意#xff1a; 题解#xff1a;
我们要先将问题转换 圈是车#xff0c;x是加油站。红色部分为车移动的路线 数组a是车数量的前缀和 数组b是加油站的前缀和 而a[i]与b[i]的差的绝对值就是对应的红色路被走的次数 现在车发生位置移动#xff0c;b数…P3992 [BJOI2017]开车
题意 题解
我们要先将问题转换 圈是车x是加油站。红色部分为车移动的路线 数组a是车数量的前缀和 数组b是加油站的前缀和 而a[i]与b[i]的差的绝对值就是对应的红色路被走的次数 现在车发生位置移动b数组没有影响a数组i到j这段整体减一 现在我们要做的就是维护a序列支持区间1/-1询问∑| a[i] - b[i] | 线段树不能实现 用分块实现 实现过程 按照下标分块每块按照a[i] - b[i] 排序
代码
代码为借鉴
#pragma optimize(Ofast)
#includebits/stdc.h
#define MAXN 150005
#define MAXB 2005
using namespace std;
typedef long long ll;int N,B,Q;
int a[MAXN], w[MAXN];
mapint,int mp;
mapint,int::iterator it;
mapint,int id;int q[MAXN][2];
struct Node{int w,val,id,sw;Node(int id0, ll val0, int w0):id(id), val(val), w(w){}bool operator (const Node n1) const{return val n1.val;}
};
vectorNode adj[MAXN];
ll ANS 0, ans[MAXN], base[MAXN];void rebuild(int id){ANS - ans[id]; ans[id] 0;sort(adj[id].begin(), adj[id].end());for(int k0;kadj[id].size();k){ans[id] abs((ll)adj[id][k].val base[id]) * adj[id][k].w;if(k0) adj[id][k].sw adj[id][k].w;else adj[id][k].sw adj[id][k-1].sw adj[id][k].w;}ANS ans[id];
}void work(int l, int r, int f){int idl l/B, idr r/B;if(idlidr){for(int k0;kadj[idl].size();k){if(ladj[idl][k].id adj[idl][k].idr){if(f0) adj[idl][k].val - 1;if(f1) adj[idl][k].val 1;}}rebuild(idl);}else{if(idl1idr){for(int ididl1;ididr;id){//int lb 0, rb adj[id].size()-1, mid;if(f0){if(adj[id][rb].val base[id] 0){ans[id] adj[id][rb].sw;ANS adj[id][rb].sw;base[id] - 1;continue;}while(lb rb){mid (lb rb)/2;if(adj[id][mid].val base[id] 0) rb mid;else lb mid 1;}base[id] - 1;int p rb;if(p0){ans[id] - adj[id][adj[id].size()-1].sw;ANS - adj[id][adj[id].size()-1].sw;}else{ans[id] adj[id][p-1].sw;ANS adj[id][p-1].sw;ans[id] - adj[id][adj[id].size()-1].sw - adj[id][p-1].sw;ANS - adj[id][adj[id].size()-1].sw - adj[id][p-1].sw;}}else{if(adj[id][rb].val base[id] 0){ans[id] - adj[id][rb].sw;ANS - adj[id][rb].sw;base[id] 1;continue;}while(lb rb){mid (lb rb)/2;if(adj[id][mid].val base[id] 0) rb mid;else lb mid 1;}base[id] 1;int p rb;if(p0){ans[id] adj[id][adj[id].size()-1].sw;ANS adj[id][adj[id].size()-1].sw;}else{ans[id] - adj[id][p-1].sw;ANS - adj[id][p-1].sw;ans[id] adj[id][adj[id].size()-1].sw - adj[id][p-1].sw;ANS adj[id][adj[id].size()-1].sw - adj[id][p-1].sw;}}}}for(int k0;kadj[idl].size();k){if(ladj[idl][k].id adj[idl][k].idr){if(f0) adj[idl][k].val - 1;if(f1) adj[idl][k].val 1;}}rebuild(idl);for(int k0;kadj[idr].size();k){if(ladj[idr][k].id adj[idr][k].idr){if(f0) adj[idr][k].val - 1;if(f1) adj[idr][k].val 1;}}rebuild(idr);}
}int pos[MAXN];int main(){scanf(%d, N);int x;for(int i1;iN;i){scanf(%d, x);pos[i] x;mp[x] 1;}for(int i1;iN;i){scanf(%d, x);mp[x] - 1;}scanf(%d, Q);for(int i1;iQ;i){scanf(%d%d, q[i][0], q[i][1]);if(mp.count(q[i][1])0) mp[q[i][1]] 0;}int n 0, x0 0;for(itmp.begin(); it!mp.end(); it){x it-first;id[x] n;w[n-1] x - x0;a[n] a[n-1] it-second;x0 x;}N n; B sqrt(N); //cerrB Bendl;for(int i1;iN;i){adj[i/B].push_back(Node(i,a[i],w[i]));}for(int id0;idN/B;id){rebuild(id);}printf(%lld\n, ANS);int l,r;for(int i1;iQ;i){l id[pos[q[i][0]]];r id[q[i][1]];pos[q[i][0]] q[i][1];//cerrwork l rendl;if(l r) work(l, r-1, 0);if(l r) work(r, l-1, 1);printf(%lld\n, ANS);}return 0;
}
