题目链接:https://darkbzoj.cf/problem/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 - 类欧几里得+线段树】
推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组