青岛网站排名多少钱,最便宜的网站叫什么名字,东莞外贸网站搭建制作,wordpress修改之前发布文章的id2022河南萌新联赛第#xff08;三#xff09;场#xff1a;河南大学\区间操作.cpp
//题意#xff1a;定义一个f[x]函数表示一个数分解质因数后各个质因子的幂次和#xff0c;给定一个长度为n的数组#xff0c;
//有m个操作#xff0c;第一种操作是输出[l, r]范围内的a…2022河南萌新联赛第三场河南大学\区间操作.cpp
//题意定义一个f[x]函数表示一个数分解质因数后各个质因子的幂次和给定一个长度为n的数组
//有m个操作第一种操作是输出[l, r]范围内的a[i]的乘积的f[i]另一种操作是整段区间乘上一个数。
//思路区间内所有数的乘积的f[i] 每个数的f[i]的和 因为数相乘 幂次方相加
//于是们开一个线段树表示区间[l, r]的f[i]和可以直接查询[l, r]范围内的a[i]的乘积的f[i]。
//对于修改一个区间乘一个v如果对v作因数分解其实就是区间加上因数分解后所有幂次的和也就是区间加我们用线段树很容易实现。
//欧拉筛预处理出范围内所有质数
#includebits/stdc.h#includeiostream#includealgorithm#includemap#includeset#includequeue#includecstring#includemath.h#includemap#includevector#includestackusing namespace std;#define endl \ntypedef pairint,int pr;#define int long long#define ll long long#define fr(i,l,r) for(int il;ir;i)#define ufr(i,n,z) for(int i n;i z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N 1e610;const int mod998244353,infLONG_LONG_MAX;int n,m;int a[N];int cnt;int st[N];int prime[N];struct node{int l,r;int sum; //和int flag;}tree[N2];void init(){ //欧拉筛for(int i2;iN;i){if(!st[i])prime[cnt]i;for(int j0;i*prime[j]N;j){st[i*prime[j]]1;if(i%prime[j]0){break;}}}}int get(int x){int ans0;if(x1) return 0;for(int i0;prime[i]*prime[i]x;i){int pprime[i];if(x%p0){while(x%p0){ans;x/p;}}}if(x1)ans;return ans;}void push_up(int p){tree[p].sumtree[p1].sumtree[p1|1].sum;}void build(int p,int l,int r){tree[p].ll;tree[p].rr;if(lr){tree[p].suma[l];return;}int midlr1;int fp1;build(f,l,mid);build(f1,mid1,r);push_up(p);}void push_down(int p){if(tree[p].flag){int fp1;tree[f].sum(tree[f].r-tree[f].l1)*tree[p].flag;tree[f1].sum(tree[f1].r-tree[f1].l1)*tree[p].flag;tree[f].flagtree[p].flag;tree[f1].flagtree[p].flag;tree[p].flag0;}}void update(int p,int l,int r,int w){if(ltree[p].ltree[p].rr){tree[p].sum(tree[p].r-tree[p].l1)*w;tree[p].flagw;return ;}push_down(p);int midtree[p].ltree[p].r1;int fp1;if(lmid)update(f,l,r,w);if(midr)update(f1,l,r,w);push_up(p);}int query(int p,int l,int r){if(ltree[p].ltree[p].rr){return tree[p].sum;}push_down(p);int ans0;int midtree[p].ltree[p].r1;int fp1;if(lmid)ansquery(f,l,r);if(midr)ansquery(f1,l,r);return ans;}void solve(){init();int n;cinn;fr(i,1,n){cina[i];a[i]get(a[i]);}build(1,1,n);int q;cinq;while(q--){int op,l,r,w;cinoplr;if(op1){cout query(1,l,r)\n;}else{cinw;wget(w);update(1,l,r,w);//cout1\n;}}}signed main(){int t1;// cint;while(t--) solve();return 0;}
2022河南萌新联赛第一场河南工业大学\热身小游戏.cpp
//给定一个数n,初始值为1
//给出q次操作
//1 a,n-n*a
//2 l r撤销第l到r操作中的1操作
//3输出nmod 1e97
//思路起初以为是可持久化线段树特地学了一下后来发现就是线段树
q次操作看做长度为q的序列操作1单点修改操作2区间修改为1操作3整个区间乘积
#include bits/stdc.h#define fr(i,l,r) for(int il;ir;i)using namespace std;#define int long long#define endl \nconst int max_n 1e5 10;const int inf 0x3f3f3f3f;const int mod 1e9 7;int n, q;struct Node{int l, r, add, v;} tr[max_n 2];void pu(int u){tr[u].v tr[u 1].v * tr[u 1 | 1].v % mod;}void pd(int u){if (tr[u].add){tr[u 1].v 1, tr[u 1 | 1].v 1;tr[u 1].add 1, tr[u 1 | 1].add 1;tr[u].add 0;}}void build(int u, int l, int r){tr[u] {l, r, 0, 1};if (l r)return;int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);pu(u);}void modify(int u, int l, int r, int c){if (tr[u].l l tr[u].r r){tr[u].add c;tr[u].v c;return;}pd(u);int mid tr[u].l tr[u].r 1;if (l mid)modify(u 1, l, r, c);if (r mid)modify(u 1 | 1, l, r, c);pu(u);}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin q;build(1, 1, q);for (int i 1; i q; i){int op;cin op;if (op 1){int a;cin a;modify(1, i, i, a); //此处单点修改不影响push_down,影响push_up}else if (op 2){int l, r;cin l r;modify(1, l, r, 1);}else if (op 3)cout tr[1].v % mod endl;}return 0;}
P3919 【模板】可持久化线段树 1可持久化数组 维护长度为N的数组的值支持以下操作 修改某个历史版本的值访问某个历史版本的值 v 1 loc value在版本v上将aloc的值改为value v 2 loc在版本v上访问aloc的值 动态开点的方法存储每个点的左右子节点 显然对于每一次修改我们都需要创造出一个新的树根 root 然后显然对于新的线段树中的任意节点如果以该节点代表的区间中不包含被修改的节点那么也就意味着以这个节点为根的子树不需要修改。 于是我们就可以让这个节点的父亲节点的与这个节点对应的儿子直接指向修改前的线段树上的该节点。 若该节点即对应被修改的节点那么就可以直接建立新节点。 若该节点对应的区间中包含该节点那么我们再对该节点的左右儿子分别处理即可。
#includebits/stdc.h
using namespace std;
const int N 2e6 10;
struct node {int l, r, t;
}tree[N 4];
int n, m, tot, a[N], root[N];//Root[i]为版本i的线段树根节点
void build(int p, int l, int r)
{p tot;//给节点赋编号if (l r) {//若当前节点只对应一点tree[p].t a[l];return;}int mid (l r) 1;build(tree[p].l, l, mid);build(tree[p].r, mid 1, r);
}
void insert(int p, int l, int r, int pos, int val, int now)//插入now为版本pos为修改点位置
{tree[p tot] tree[now];//使当前路径上的点等于原来版本上的对应点if (l r) {tree[p].t val;return;}int mid (l r) 1;if (pos mid)insert(tree[p].l, l, mid, pos, val, tree[now].l);elseinsert(tree[p].r, mid 1, r, pos, val, tree[now].r);
}
int query(int p, int l, int r, int pos)
{if (l r)return tree[p].t;int mid (l r) 1;if (pos mid)return query(tree[p].l, l, mid, pos);elsereturn query(tree[p].r, mid 1, r, pos);
}
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i)scanf(%d, a i);build(root[0], 1, n);for (int i 1; i m; i) {int opt, v, loc, val;//opt为操作种类v为版本loc为修改/查询点位置val为修改值scanf(%d%d%d, v, opt, loc);if (opt 1) {scanf(%d, val);insert(root[i], 1, n, loc, val, root[v]);}elseprintf(%d\n, query(root[i] root[v], 1, n, loc));//查询同时因为查询生成不变的新版本所以Root[i]Root[v]}return 0;
}
牛客\多校\2022河南萌新联赛第二场河南理工大学\数对.cpp
//给定2e5的数列x,y
//1lrn
//求多少对(l,r)满足al...arxy*(r-l1) (-1e9ai1e9)
//思路转化成(al-y)....(ar-y)x令biai-y,求前缀和
//进一步转化成sumr-sumlx,sumr-xsuml枚举右端点每次累加树状数组大于等于sumr-x的个数
//值域很大树状数组装不下考虑离散化 #includebits/stdc.h#includeiostream#includealgorithm#includemap#includeset#includequeue#includecstring#includemath.h#includemap#includevector#includestackusing namespace std;#define endl \ntypedef pairint,int pr;#define int long long#define ll long long#define fr(i,l,r) for(int il;ir;i)#define ufr(i,n,z) for(int i n;i z; i--)#define pb(x) push_back(x)#define all(a) a.begin(),a.end()#define fi first#define se secondconst int N 1e610;const int mod998244353,infLONG_LONG_MAX;int n,m;int a[N];int tree[N];int sum[N];vectorintv;int lowbit(int x){return x(-x);}void add(int x){for(int ix;iN;ii-i){tree[i]1;}}int query(int x){int ans0;for(int ix;i;i-i-i){anstree[i];}return ans;}int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()1;}void solve(){int x,y;cinnxy;fr(i,1,n){cinsum[i];sum[i]sum[i-1]-y;}fr(i,0,n){v.push_back(sum[i]);v.push_back(sum[i]-x);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());int ans0;fr(i,0,n){ansi-query(get(sum[i]-x)-1);add(get(sum[i]));}coutans\n;}signed main(){int t1;// cint;while(t--) solve();return 0;}
