做网站创业故事,企业网站的制作与维护,织梦古典网站模板,非凡软件站目录 descriptionsolutionaccepted codedetailsdescription 请你维护一个序列#xff0c;支持两种操作#xff1a; #xff08;1#xff09;某个区间 [x, y] 内的数同时加上一个增量 k。 #xff08;2#xff09;询问某一个区间 [x, y] 中从 1 开始的最大前缀和。 input … 目录 descriptionsolutionaccepted codedetails description 请你维护一个序列支持两种操作 1某个区间 [x, y] 内的数同时加上一个增量 k。 2询问某一个区间 [x, y] 中从 1 开始的最大前缀和。 input 第一行给出一个整数 n。n 100000。接下来一行 n 个整数表示序列的初始值。 第三行给出一个整数 mm 100000。接下来 m 行每行一个操作。 1 0 x y k表示给区间 [x, y] 同时加上 k。 2 1 x y询问区间 [x, y]。output 对于每个询问输出一个整数表示最大前缀和。 sample input 5 1 8 -8 3 -7 3 1 1 5 0 1 3 6 1 2 4sample output 9 22 solution 我们考虑直接维护前缀和序列则操作2就是在查询区间最大值。 而对于操作1我们相当于两部分操作 对于 x i y给 i 位置加上 (i-x1)*k对于 y i给 i 位置加上 (y-x1)*k。 前一个可以拆成 (-x1)*k i*k是常数 系数*位置的形式后面那个也可以看成这种形式只是位置前面的系数为 0。 看起来还是不好维护但是我们可以注意到这样一件事情对于某一个位置 i它的值总是形如 k*i b 的形式。 直线解析式。所以我们考虑用几何方法来维护这种东西。几何方法当然首先想到凸包。 每次操作相当于给区间内所有点的斜率与截距同时加上增量手算一下会发现这个区间相邻两点之间的斜率也会同时增加 k这样也就是说这个区间的凸包形状不会变化。 线段树不太好搞况且这道题时限 50s 我们考虑使用分块算法来维护凸包。 修改时散块暴力修改并重构凸包整块打标记记录这个区间整体的斜率与截距变化量。 查询时散块暴力求答案整块凸包上二分。 时间复杂度 \(O(n\sqrt{n}\log n)\) accepted code #includecstdio
#includealgorithm
using namespace std;
typedef long long ll;
const int MAXN 100000;
const int BLOCK 320;
const ll INF (1ll62);
ll sp[BLOCK 5], b1[MAXN 5], b2[BLOCK 5];
int le[BLOCK 5], ri[BLOCK 5], num[MAXN 5];
int stk[MAXN 5], tp[BLOCK 5], n, m, bcnt 0;
ll get_ans(int x) {return sp[num[x]]*x b1[x] b2[num[x]];
}
ll query(int x) {int l le[x], r tp[x];while( l r ) {int mid (l r) 1;if( get_ans(stk[mid]) get_ans(stk[mid1]) ) r mid;else l mid 1;}return get_ans(stk[r]);
}
void push_tag(int x) {for(int ile[x];iri[x];i)b1[i] get_ans(i);sp[x] b2[x] 0;
}
void build(int x) {tp[x] le[x] - 1;for(int ile[x];iri[x];i) {while( tp[x] le[x] (get_ans(i) - get_ans(stk[tp[x]]))*(stk[tp[x]] - stk[tp[x] - 1]) (get_ans(stk[tp[x]])-get_ans(stk[tp[x] - 1]))*(i - stk[tp[x]]) )tp[x]--;stk[tp[x]] i;}
}
void init() {for(int i0;in;i) {if( i % BLOCK 0 ) {num[i] (bcnt);le[num[i]] ri[num[i]] i;sp[num[i]] b2[num[i]] 0;}else ri[num[i] bcnt];}
}
int main() {scanf(%d, n); init();for(int i0;in;i)scanf(%lld, b1[i]), b1[i] b1[i-1];for(int i1;ibcnt;i)build(i);scanf(%d, m);for(int i1;im;i) {int op, x, y; ll k;scanf(%d%d%d, op, x, y);x--, y--;if( op 0 ) {scanf(%lld, k);if( num[x] ! num[y] ) {push_tag(num[x]), push_tag(num[y]);for(int ix;iri[num[x]];i)b1[i] k*(i-x1);for(int ile[num[y]];iy;i)b1[i] k*(i-x1);for(int iy1;iri[num[y]];i)b1[i] k*(y-x1);build(num[x]), build(num[y]);for(int inum[x]1;inum[y]-1;i)sp[i] k, b2[i] k*(-x1);}else {push_tag(num[x]);for(int ix;iy;i)b1[i] k*(i-x1);for(int iy1;iri[num[y]];i)b1[i] k*(y-x1);build(num[x]);}for(int inum[y]1;ibcnt;i)b2[i] k*(y-x1);}else {ll ans -INF;if( num[x] ! num[y] ) {for(int ix;iri[num[x]];i)ans max(ans, get_ans(i));for(int ile[num[y]];iy;i)ans max(ans, get_ans(i));for(int inum[x]1;inum[y]-1;i)ans max(ans, query(i));}else {for(int ix;iy;i)ans max(ans, get_ans(i));}printf(%lld\n, ans);}}
} details 突然发现这是我第一次写分块原来我以前从来没写过这种东西 把分块的左端点右端点以及每个点属于哪个块先预处理出来感觉比较好写。 并且把块的大小设置为常数也是一个不错的懒人做法虽然想想都知道这样肯定常数大。转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/10262494.html
