做彩票网站需要学习什么,廊坊市固安县建设局网站,网站建设公司的组织架构,企业网怎么拉正题
题目链接:https://www.luogu.com.cn/problem/P6688 解题思路 nnn个数#xff0c;每次有操作
修改一个数询问两个区间是否他们中的元素分别组成的可重集合A,BA,BA,B#xff0c;满足对于每个AiBikA_iB_ikAiBik其中kkk是一个相同的数 解题思路
先不考虑kkk的问题 我…正题
题目链接:https://www.luogu.com.cn/problem/P6688 解题思路
nnn个数每次有操作
修改一个数询问两个区间是否他们中的元素分别组成的可重集合A,BA,BA,B满足对于每个AiBikA_iB_ikAiBik其中kkk是一个相同的数 解题思路
先不考虑kkk的问题 我们字符串hashhashhash的特征值是第iii位为pip^ipi但是我们这边并不考虑它的顺序然后可重集合提示我们要构造集合的特征值。那么我们对于一个数xxx它的特征值是pxp^xpx若一个集合中有cic_ici个iii那么这个集合的特征值就是∑i1∞pici\sum_{i1}^{\infty}p^ic_i∑i1∞pici即可。
如果考虑kkk怎么做那么满足条件的话就是满足AiA_iAi中的每个数都比BiB_iBi多kkk所以我们只需要求出A,BA,BA,B的元素和的差然后除以它们的大小就是kkk了然后小的那个特征值乘上一个pkp^kpk比较即可。
线段树维护区间特征值和区间和因为卡了自然溢出需要自己设定模数时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
#define ull unsigned long long
using namespace std;
const ll N1e610;
const ull p1145141,P1e97;
ull pw[N],w[N2];
ll n,q,v[N2],a[N];
void Build(ll x,ll l,ll r){if(lr){w[x]pw[a[l]];v[x]a[l];return;} ll mid(lr)1;Build(x*2,l,mid);Build(x*21,mid1,r);w[x](w[x*2]w[x*21])%P;v[x]v[x*2]v[x*21];return;
}
void Change(ll x,ll l,ll r,ll pos,ll val){if(lr){w[x]pw[val];v[x]val;return;}ll mid(lr)1;if(posmid)Change(x*2,l,mid,pos,val);else Change(x*21,mid1,r,pos,val);w[x](w[x*2]w[x*21])%P;v[x]v[x*2]v[x*21];return;
}
void Ask(ll x,ll L,ll R,ll l,ll r,ull sw,ll sv){if(LlRr){(sww[x])%P;svv[x];return;}ll mid(LR)1;if(rmid)Ask(x*2,L,mid,l,r,sw,sv);else if(lmid)Ask(x*21,mid1,R,l,r,sw,sv);else Ask(x*2,L,mid,l,mid,sw,sv),Ask(x*21,mid1,R,mid1,r,sw,sv);return;
}
int main()
{scanf(%lld%lld,n,q);pw[0]1;for(ll i1;i1e6;i)pw[i]pw[i-1]*p%P;for(ll i1;in;i)scanf(%lld,a[i]);Build(1,1,n);while(q--){ll op;scanf(%lld,op);if(op0){ll x,y;scanf(%lld%lld,x,y);Change(1,1,n,x,y);}else{ll l0,r0,l1,r1,sv00,sv10;ull sw00,sw10;scanf(%lld%lld%lld%lld,l0,r0,l1,r1);Ask(1,1,n,l0,r0,sw0,sv0);Ask(1,1,n,l1,r1,sw1,sv1);if(sv1sv0)swap(sv0,sv1),swap(sw0,sw1);if((sv1-sv0)%(r1-l11)){printf(NO\n);continue;}ll k(sv1-sv0)/(r1-l11);sw0sw0*pw[k]%P;if(sw0sw1)printf(YES\n);else printf(NO\n);}}return 0;
}
