购物网站app推广方案,网站如何添加统计代码是什么,wordpress 旋转加载,请问聊城做网站昨天晚上做完4题还有30分钟#xff0c;感觉太晚了就没继续写#xff0c;不过看了下E题感觉是一个线段树题目#xff0c;今天中午看了看发现就是一个线段树上递归的询问问题#xff0c;不过我之前没写过但是靠着日益强大的乱写能力竟然水出来了~~
E. Greedy Shopping
不难…昨天晚上做完4题还有30分钟感觉太晚了就没继续写不过看了下E题感觉是一个线段树题目今天中午看了看发现就是一个线段树上递归的询问问题不过我之前没写过但是靠着日益强大的乱写能力竟然水出来了~~
E. Greedy Shopping
不难知道操作1并不改变原数组不升序的性质即非严格单调递减的性质永远存在。
操作一在线段树上二分第一个小于y的数的位置pos然后区间修改即可[pos→x][pos\to x][pos→x] 操作二维护一个区间最小值和区间和然后递归乱搞由于每次能买则买先往左子树递归然后记录一下左子树的花费再往右子树递归这时候剩余的钱要减去左子树的花费全局变量记录答案。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N400010;
ll a[N];
int n,q;
struct node
{int l,r;ll sum,mn;ll lazy;
}tree[N*4];
void pushup(int u)
{tree[u].sumtree[u1].sumtree[u1|1].sum;tree[u].mnmin(tree[u1].mn,tree[u1|1].mn);
}
void pushdown(int u)
{if(!tree[u].lazy)return;tree[u1].sum(tree[u1].r-tree[u1].l1)*tree[u].lazy;tree[u1|1].sum(tree[u1|1].r-tree[u1|1].l1)*tree[u].lazy;tree[u1].mntree[u1|1].mntree[u].lazy;tree[u1].lazytree[u1|1].lazytree[u].lazy;tree[u].lazy0;
}
void build(int u,int l,int r)
{tree[u]{l,r};if(lr) {tree[u].sumtree[u].mna[l];return;}int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);
}
void modify(int u,int l,int r,ll val)
{if(tree[u].lltree[u].rr){tree[u].lazytree[u].mnval;tree[u].sum(tree[u].r-tree[u].l1)*val;return;}pushdown(u);int midtree[u].ltree[u].r1;if(lmid) modify(u1,l,r,val);if(rmid) modify(u1|1,l,r,val);pushup(u);
}
int findmn(int u,ll val)
{if(tree[u].ltree[u].r) return tree[u].l;pushdown(u);if(tree[u1].mnval) return findmn(u1|1,val);else return findmn(u1,val);
}
int ans;
int calc(int u,int l,int r,ll now)
{if(tree[u].rl||tree[u].lr||!now) return 0;if(tree[u].lltree[u].rr){if(tree[u].sumnow){anstree[u].r-tree[u].l1;return tree[u].sum;}}ll w0;pushdown(u);int midtree[u].ltree[u].r1;if(lmidtree[u1].mnnow) wcalc(u1,l,r,now);if(rmid) wcalc(u1|1,l,r,now-w);return w;
}
int main()
{IO;int T1;//cinT;while(T--){cinnq;for(int i1;in;i) cina[i];build(1,1,n1);while(q--){int op,x,y;cinopxy;if(op1){int posfindmn(1,y);if(posx) modify(1,pos,x,y); }else{ans0;calc(1,x,n,y);coutans\n;}}}return 0;
}此代码必须在多开一倍空间要不然calc函数越界我也不知道为啥很迷 要加哟哦~
