锐客网

  1. 首页 > it技术 > >

数论|bzoj 1938 - 类欧几里得+线段树

数论线段树

题目链接:https://darkbzoj.cf/problem/1938

解题思路；
对于区间更新:
数论|bzoj 1938 - 类欧几里得+线段树
文章图片

前半部分可以用线段树求等差数列和,后半部分可以用类欧几里得算法求出值
类欧几里得
然后是要对区间离散化,其中有个问题在于对于区间(l,r)分裂为(l,mid)和(mid+1,r)都是mid-mid+1中还有值,
所以对于区间(l,r)实际包含的是(num[r+1]-num[l]),num[r+1]位置不算,所以在插入s[i].R时是加入s[i].R+1使得边界没有算入其中.

#include #include #include #include #include #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef __int128 ll; const int mod = 1e9; const int mx = 1e5 + 10; int n,num[mx<<1],A,B,m,d; struct node { int f; int L,R,A,B; }s[mx]; ll sum[mx<<2]; int a[mx<<2],b[mx<<2],beg[mx<<2]; ll find(int x,int y,int z,ll len) { if(!x) return (len+1)*(y/z); if(len<0) return 0; if(x>=z||y>=z){ return find(x%z,y%z,z,len) + (x/z)*len*(len+1)/2 + (len+1)*(y/z); } ll up = (x*len+y)/z; return len*up - find(z,z-y-1,x,up-1); } void calc(int rt,int l,int r) { ll N = (num[r+1]-num[l]); ll less = find(a[rt],0,b[rt],num[r+1]-1-beg[rt]) - find(a[rt],0,b[rt],num[l]-1-beg[rt]); less *= b[rt]; sum[rt] = N*(num[l]-beg[rt])*a[rt]+(N*(N-1))/2*a[rt] - less; } void push_up(int l,int r,int rt) { int mid = (l+r)>>1; if(b[rt]){ a[rt<<1] = a[rt<<1|1] = a[rt]; b[rt<<1] = b[rt<<1|1] = b[rt]; beg[rt<<1] = beg[rt<<1|1] = beg[rt]; calc(rt<<1,l,mid); calc(rt<<1|1,mid+1,r); b[rt] = 0; } } void update(int l,int r,int rt,int L,int R) { if(L<=l&&r<=R){ a[rt] = A,b[rt] = B; beg[rt] = d; calc(rt,l,r); return ; } push_up(l,r,rt); int mid = (l+r)>>1; if(L<=mid) update(lson,L,R); if(R>mid) update(rson,L,R); sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } long long int query(int l,int r,int rt,int L,int R) { if(L<=l&&r<=R) return sum[rt]; push_up(l,r,rt); int mid = (l+r)>>1; long long int ans = 0; if(L<=mid) ans += query(lson,L,R); if(R>mid) ans += query(rson,L,R); return ans; } int main() { int x,L,R; int top = 0; scanf("%d%d",&m,&n); for(int i=0; i

【数论|bzoj 1938 - 类欧几里得+线段树】

    推荐阅读


    上一篇：谷歌 Chrome 97 推出 keyboard MAP API 再引争议（业内“对家”纷纷抵制）

    下一篇：高仿QQ、微信效果的图片浏览器（支持原图和缩略图、多种手势、CocoaPods）