尽量不要全局long long
尽量不要全局long long
尽量不要全局long long
尽量不要全局long long
尽量不要全局long long
尽量不要全局long long
目录
ST表
int n,m;
const int N=5e4+10,M=log2(N)+10;
int a[N];
int f[N][M][2];
void st()
{
for(int i=1;i<=n;i++)f[i][0][0]=f[i][0][1]=a[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j][0]=max(f[i][j-1][0],f[i+(1<<(j-1))][j-1][0]),
f[i][j][1]=min(f[i][j-1][1],f[i+(1<<(j-1))][j-1][1]);
}
int query(int l,int r,bool sign)
{
int len=r-l+1;
int q=log2(len);
if(!sign)return max(f[l][q][0],f[r-((1<<q))+1][q][0]);
else return min(f[l][q][1],f[r-((1<<q))+1][q][1]);
}
分块
const int N=1e5+10,M=350;
int n,m;
int len;//len=sqrt(n)时间最优
int a[N];
long long b[M],s[M];
//a表示数据数组，b记录每个块的整体赋值情况(懒标记),s块内元素和
int get(int x)//属于哪个块
{
return (x-1)/len;
}
void modify(int l,int r,int val)
{
if(get(l)==get(r))
{
rep(i,l,r)a[i]+=val,s[get(i)]+=val;
}
else
{
int i=l,j=r;
while(get(i)==get(l))a[i]+=val,s[get(i)]+=val,i++;
while(get(j)==get(r))a[j]+=val,s[get(j)]+=val,j--;
rep(k,get(i),get(j))s[k]+=val*len,b[k]+=val;
}
}
long long query(int l,int r)
{
long long res=0;
if(get(l)==get(r))
{
rep(i,l,r)res+=a[i]+b[get(i)];
}
else
{
int i=l,j=r;
while(get(i)==get(l))res+=a[i]+b[get(i)],i++;
while(get(j)==get(r))res+=a[j]+b[get(j)],j--;
rep(k,get(i),get(j))res+=s[k];
}
return res;
}
void solve()
{
cin>>n>>m;
len=sqrtl(n);//均值不等式
rep(i,1,n)
{
cin>>a[i];
s[get(i)]+=a[i];
}
while(m--)
{
char op;
cin>>op;
if(op=='C')
{
int l,r,x;
cin>>l>>r>>x;
modify(l,r,x);
}
else
{
int l,r;
cin>>l>>r;
cout<<query(l,r)<<endl;
}
}
}
线段树
线段树上二分
int find(int k,int l,int r,int val)//找整个区间范围找第val个1的下标
{
if(l==r)return l;
push_down(k,l,r);
int mid=l+r>>1;
if(val<=tr[k<<1].val)return find(k<<1,l,mid,val);
else return find(k<<1|1,mid+1,r,val-tr[k<<1].val);//关键是这一步
}
int ask1(int k,int l,int r,int pos)//第一个大于等于pos的1的位置
{
if(r<pos||tr[k].val==0)return -1;
if(l==r)return l;
push_down(k,l,r);
int mid=l+r>>1;
int t=ask1(k<<1,l,mid,pos);
if(~t)return t;
return ask1(k<<1|1,mid+1,r,pos);
}
int ask0(int k,int l,int r,int pos)//第一个大于等于pos的0的位置
{
if(r<pos||r-l+1-tr[k].val==0)return -1;
if(l==r)return l;
push_down(k,l,r);
int mid=l+r>>1;
int t=ask0(k<<1,l,mid,pos);
if(~t)return t;
return ask0(k<<1|1,mid+1,r,pos);
}
int ans(int k,int l,int r)//右边第一个1的位置
{
if(l==r)return l;
push_down(k,l,r);
int mid=l+r>>1;
if(tr[k<<1|1].val)return ans(k<<1|1,mid+1,r);
return ans(k<<1,l,mid);
}
单点修改，区间查值
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long//高精度关掉此
#define LL long long
#define ull unsigned long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){
return (a%mod+mod)%mod;}
int lowbit(int x){
return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){
int res = 1 % p;while (k){
if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){
return qmi(a,mod-2,mod);}
int lcm(int a,int b){
return a*b/__gcd(a,b);}
const int N=5e5+10;
int n,m;
struct node
{
int l,r;
int val;
}tr[N<<2];
int a[N];
void push_up(int u)
{
tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{
tr[k].val=a[l];
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int pos,int val)
{
if(l==r)
{
tr[k].val+=val;
return;
}
int mid=l+r>>1;
if(pos<=mid)modify(k<<1,l,mid,pos,val);
else modify(k<<1|1,mid+1,r,pos,val);
push_up(k);
}
int query(int k,int l,int r,int x,int y)
{
if(x>r||y<l)return 0;
if(x<=l&&y>=r)return tr[k].val;
int mid=l+r>>1;
int res=0;
if(x<=mid)res+=query(k<<1,l,mid,x,y);
if(y>=mid+1)res+=query(k<<1|1,mid+1,r,x,y);
return res;
}
void solve()
{
cin>>n>>m;
rep(i,1,n)cin>>a[i];
build(1,1,n);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,k;
cin>>x>>k;
modify(1,1,n,x,k);
}
else
{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<endl;
}
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
区间xor，区间最长1 or 0 的长度
#include <bits/stdc++.h>
using namespace std;
//==================debug
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
//==================DFFINE
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long//高精度关掉此
#define LL long long
#define ull unsigned long long
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define PDD pair<double,double>
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
//==================HABIT
int Mod(int a,int mod){
return (a%mod+mod)%mod;}
int lowbit(int x){
return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){
int res = 1 % p;a%=p;while (k){
if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){
return qmi(a,mod-2,mod);}
const int N=1e6+10;
struct node
{
int l,r;
int maxv1,maxv0;//区间最大1串，0串长度
int maxvl1,maxvr1;
int maxvl0,maxvr0;
int lz;//xor_lazy
}tr[N<<2];
int a[N];
int n,m;
void push_up(int k)
{
tr[k].maxvl1=tr[k<<1].maxvl1;
if(tr[k<<1].maxv1==tr[k<<1].r-tr[k<<1].l+1)tr[k].maxvl1=tr[k<<1].maxv1+tr[k<<1|1].maxvl1;
tr[k].maxvr1=tr[k<<1|1].maxvr1;
if(tr[k<<1|1].maxv1==tr[k<<1|1].r-tr[k<<1|1].l+1)tr[k].maxvr1=tr[k<<1|1].maxv1+tr[k<<1].maxvr1;
tr[k].maxv1=max(max(tr[k<<1].maxv1,tr[k<<1|1].maxv1),tr[k<<1].maxvr1+tr[k<<1|1].maxvl1);
tr[k].maxvl0=tr[k<<1].maxvl0;
if(tr[k<<1].maxv0==tr[k<<1].r-tr[k<<1].l+1)tr[k].maxvl0=tr[k<<1].maxv0+tr[k<<1|1].maxvl0;
tr[k].maxvr0=tr[k<<1|1].maxvr0;
if(tr[k<<1|1].maxv0==tr[k<<1|1].r-tr[k<<1|1].l+1)tr[k].maxvr0=tr[k<<1|1].maxv0+tr[k<<1].maxvr0;
tr[k].maxv0=max(max(tr[k<<1].maxv0,tr[k<<1|1].maxv0),tr[k<<1].maxvr0+tr[k<<1|1].maxvl0);
}
void push_down(int k,int l,int r)
{
if(tr[k].lz)
{
tr[k<<1].lz^=1,tr[k<<1|1].lz^=1;
swap(tr[k<<1].maxvl0,tr[k<<1].maxvl1);
swap(tr[k<<1].maxvr0,tr[k<<1].maxvr1);
swap(tr[k<<1].maxv0,tr[k<<1].maxv1);
swap(tr[k<<1|1].maxvl0,tr[k<<1|1].maxvl1);
swap(tr[k<<1|1].maxvr0,tr[k<<1|1].maxvr1);
swap(tr[k<<1|1].maxv0,tr[k<<1|1].maxv1);
tr[k].lz^=1;
}
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
tr[k].lz=0;
if(l==r)
{
if(a[l]==1)tr[k].maxvl1=tr[k].maxvr1=tr[k].maxv1=1,tr[k].maxvl0=tr[k].maxvr0=tr[k].maxv0=0;
else tr[k].maxvl0=tr[k].maxvr0=tr[k].maxv0=1,tr[k].maxvl1=tr[k].maxvr1=tr[k].maxv1=0;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
tr[k].lz^=1;
swap(tr[k].maxvl0,tr[k].maxvl1);
swap(tr[k].maxvr0,tr[k].maxvr1);
swap(tr[k].maxv0,tr[k].maxv1);
return;
}
push_down(k,l,r);
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,y);
if(y>=mid+1) modify(k<<1|1,mid+1,r,x,y);
push_up(k);
}
node query(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return tr[k];
push_down(k,l,r);
int mid=l+r>>1;
if(y<=mid)return query(k<<1,l,mid,x,y);
else if(x>=mid+1)return query(k<<1|1,mid+1,r,x,y);
else
{
auto L=query(k<<1,l,mid,x,y);
auto R=query(k<<1|1,mid+1,r,x,y);
node res;
res.maxv1=max(max(L.maxv1,R.maxv1),L.maxvr1+R.maxvl1);
res.maxvl1=L.maxvl1;
if(L.maxv1==L.r-L.l+1)res.maxvl1=L.maxv1+R.maxvl1;
res.maxvr1=R.maxvr1;
if(R.maxv1=R.r-R.l+1)res.maxvr1=R.maxv1+L.maxvr1;
res.maxv0=max(max(L.maxv0,R.maxv0),L.maxvr0+R.maxvl0);
res.maxvl0=L.maxvl0;
if(L.maxv0==L.r-L.l+1)res.maxvl0=L.maxv0+R.maxvl0;
res.maxvr0=R.maxvr0;
if(R.maxv0=R.r-R.l+1)res.maxvr0=R.maxv0+L.maxvr0;
return res;
}
}
/* 8 1 10001101 Q 1 3 */
void solve()
{
cin>>n>>m;
string s;
cin>>s;
rep(i,1,n)a[i]=s[i-1]-'0';
build(1,1,n);
while(m--)
{
char c;
int x,y;
cin>>c>>x>>y;
if(c=='Q')
{
node res=query(1,1,n,x,y);
cout<<max(res.maxv1,res.maxv0)<<endl;
}
else
{
modify(1,1,n,x,y);
}
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
rep(i,1,_)solve();
return 0;
}
单点修改，单点(映射区间)查询
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long//高精度关掉此
#define LL long long
#define ull unsigned long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){
return (a%mod+mod)%mod;}
int lowbit(int x){
return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){
int res = 1 % p;while (k){
if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){
return qmi(a,mod-2,mod);}
int lcm(int a,int b){
return a*b/__gcd(a,b);}
const int N=5e5+10;
struct node
{
int l,r;
int maxvl,maxvr,maxv;
}tr[N<<2];
int a[N];
int n,m;
void push_up(int k)
{
tr[k].maxvl=tr[k<<1].maxvl;
if(tr[k<<1].maxv==tr[k<<1].r-tr[k<<1].l+1)tr[k].maxvl=tr[k<<1].maxv+tr[k<<1|1].maxvl;
tr[k].maxvr=tr[k<<1|1].maxvr;
if(tr[k<<1|1].maxv==tr[k<<1|1].r-tr[k<<1|1].l+1)tr[k].maxvr=tr[k<<1|1].maxv+tr[k<<1].maxvr;
tr[k].maxv=max(max(tr[k<<1].maxv,tr[k<<1|1].maxv),tr[k<<1].maxvr+tr[k<<1|1].maxvl);
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{
tr[k].maxvl=tr[k].maxvr=tr[k].maxv=a[l];
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int x,int val)
{
if(l==r)
{
tr[k].maxvl=tr[k].maxvr=tr[k].maxv=val;
return;
}
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,val);
else modify(k<<1|1,mid+1,r,x,val);
push_up(k);
}
int query(int k,int l,int r,int x)
{
if(l==r)return tr[k].maxv;
int mid=l+r>>1;
if(x>=mid-tr[k<<1].maxvr+1&&x<=mid+tr[k<<1|1].maxvl)//x属于这一段区间
return tr[k<<1].maxvr+tr[k<<1|1].maxvl;
if(x<=mid)return query(k<<1,l,mid,x);
else return query(k<<1|1,mid+1,r,x);
}
void solve()
{
while(cin>>n>>m)
{
stack<int>stk;
rep(i,1,n)a[i]=1;
build(1,1,n);
rep(i,1,m)
{
char op;
cin>>op;
if(op=='D')
{
int x;
cin>>x;
stk.push(x);
modify(1,1,n,x,0);
}
else if(op=='Q')
{
int x;
cin>>x;
cout<<query(1,1,n,x)<<endl;
}
else
{
if(stk.size())modify(1,1,n,stk.top(),1);
else modify(1,1,n,0,1);
if(stk.size())stk.pop();
}
}
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
rep(i,1,_)solve();
return 0;
}
求[x,y]最大连续子段和
const int N=5e5+10;
int a[N];
int n,m;
struct node
{
int l,r;
int val,maxvl,maxvr,maxv;
}tr[N<<2];
void push_up(int k)
{
tr[k].val=tr[k<<1].val+tr[k<<1|1].val;
tr[k].maxvl=max(tr[k<<1].maxvl,tr[k<<1].val+tr[k<<1|1].maxvl);
tr[k].maxvr=max(tr[k<<1|1].maxvr,tr[k<<1|1].val+tr[k<<1].maxvr);
tr[k].maxv=max(max(tr[k<<1].maxv,tr[k<<1|1].maxv),tr[k<<1].maxvr+tr[k<<1|1].maxvl);
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{
tr[k].val=tr[k].maxv=tr[k].maxvl=tr[k].maxvr=a[l];
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int x,int val)
{
if(l==r)
{
tr[k].val=tr[k].maxv=tr[k].maxvl=tr[k].maxvr=val;
return;
}
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,val);
else modify(k<<1|1,mid+1,r,x,val);
push_up(k);
}
node query(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return tr[k];
int mid=l+r>>1;
if(y<=mid)return query(k<<1,l,mid,x,y);
else if(x>=mid+1)return query(k<<1|1,mid+1,r,x,y);
else
{
auto L=query(k<<1,l,mid,x,y);
auto R=query(k<<1|1,mid+1,r,x,y);
node res;
res.val=L.val+R.val;
res.maxvl=max(L.maxvl,L.val+R.maxvl);
res.maxvr=max(R.maxvr,R.val+L.maxvr);
res.maxv=max(max(L.maxv,R.maxv),L.maxvr+R.maxvl);
return res;
}
}
区间修改，区间查值
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long//高精度关掉此
#define LL long long
#define ull unsigned long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){
return (a%mod+mod)%mod;}
int lowbit(int x){
return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){
int res = 1 % p;while (k){
if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){
return qmi(a,mod-2,mod);}
int lcm(int a,int b){
return a*b/__gcd(a,b);}
const int N=5e5+10;
int n,m;
struct node
{
int l,r;
int lz;
int val;
}tr[N<<2];
int a[N];
void push_up(int k)
{
tr[k].val=tr[k<<1].val+tr[k<<1|1].val;
}
void push_down(int k,int l,int r)
{
if(tr[k].lz)
{
int mid=l+r>>1;
tr[k<<1].lz+=tr[k].lz;
tr[k<<1|1].lz+=tr[k].lz;
tr[k<<1].val+=tr[k].lz*(mid-l+1);
tr[k<<1|1].val+=tr[k].lz*(r-mid);
tr[k].lz=0;
}
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r;
if(l==r)
{
tr[k].val=a[l];
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int x,int y,int p)
{
if(x<=l&&y>=r)
{
tr[k].val+=(r-l+1)*p;
tr[k].lz+=p;
return;
}
push_down(k,l,r);
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,y,p);
if(y>=mid+1)modify(k<<1|1,mid+1,r,x,y,p);
push_up(k);
}
int query(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return tr[k].val;
push_down(k,l,r);
int mid=l+r>>1;
int res=0;
if(x<=mid)res+=query(k<<1,l,mid,x,y);
if(y>=mid+1)res+=query(k<<1|1,mid+1,r,x,y);
return res;
}
void solve()
{
cin>>n>>m;
rep(i,1,n)cin>>a[i];
build(1,1,n);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,k;
cin>>x>>y>>k;
modify(1,1,n,x,y,k);
}
else
{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<endl;
}
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
例题
将某区间每一个数乘上 x
将某区间每一个数加上 x
求出某区间每一个数的和
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long//高精度关掉此
#define LL long long
#define ull unsigned long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){
return (a%mod+mod)%mod;}
int lowbit(int x){
return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){
int res = 1 % p;while (k){
if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){
return qmi(a,mod-2,mod);}
int lcm(int a,int b){
return a*b/__gcd(a,b);}
const int N=1e5+10;
int n,m,p;
struct node
{
int l,r;
int lz_add;
int lz_mul;
int val;
}tr[N<<2];
int a[N];
void push_up(int k)
{
tr[k].val=(tr[k<<1].val+tr[k<<1|1].val)%p;
}
void push_down(int k,int l,int r)
{
int mid=l+r>>1;
tr[k<<1].lz_add=(tr[k<<1].lz_add*tr[k].lz_mul+tr[k].lz_add)%p;
tr[k<<1|1].lz_add=(tr[k<<1|1].lz_add*tr[k].lz_mul+tr[k].lz_add)%p;
tr[k<<1].lz_mul=(tr[k<<1].lz_mul*tr[k].lz_mul)%p;
tr[k<<1|1].lz_mul=(tr[k<<1|1].lz_mul*tr[k].lz_mul)%p;
tr[k<<1].val=(tr[k<<1].val*tr[k].lz_mul+tr[k].lz_add*(mid-l+1))%p;
tr[k<<1|1].val=(tr[k<<1|1].val*tr[k].lz_mul+tr[k].lz_add*(r-mid))%p;
tr[k].lz_mul=1;
tr[k].lz_add=0;
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r,tr[k].lz_mul=1;
if(l==r)
{
tr[k].val=a[l]%p;
return;
}
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify_mul(int k,int l,int r,int x,int y,int val)
{
if(x<=l&&y>=r)
{
tr[k].lz_add=(tr[k].lz_add*val)%p;
tr[k].lz_mul=(tr[k].lz_mul*val)%p;
tr[k].val=(tr[k].val*val)%p;
return;
}
push_down(k,l,r);
int mid=l+r>>1;
if(x<=mid)modify_mul(k<<1,l,mid,x,y,val);
if(y>=mid+1)modify_mul(k<<1|1,mid+1,r,x,y,val);
push_up(k);
}
void modify_add(int k,int l,int r,int x,int y,int val)
{
if(x<=l&&y>=r)
{
tr[k].lz_add=(tr[k].lz_add+val)%p;
tr[k].val=(tr[k].val+val*(r-l+1))%p;
return;
}
push_down(k,l,r);
int mid=l+r>>1;
if(x<=mid)modify_add(k<<1,l,mid,x,y,val);
if(y>=mid+1)modify_add(k<<1|1,mid+1,r,x,y,val);
push_up(k);
}
int query(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return tr[k].val%p;
push_down(k,l,r);
int mid=l+r>>1;
int res=0;
if(x<=mid)res=(res+query(k<<1,l,mid,x,y))%p;
if(y>=mid+1)res=(res+query(k<<1|1,mid+1,r,x,y))%p;
return res;
}
void solve()
{
cin>>n>>m>>p;
rep(i,1,n)cin>>a[i];
build(1,1,n);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,k;
cin>>x>>y>>k;
modify_mul(1,1,n,x,y,k);
}
else if(op==2)
{
int x,y,k;
cin>>x>>y>>k;
modify_add(1,1,n,x,y,k);
}
else if(op==3)
{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<endl;
}
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
onst int N=1e5+10;
int n,m,mod=10007;
struct node
{
int l,r;
int val;
int mul,add;
int val2,val3;
}tr[N<<2];
void push_up(int k)
{
tr[k].val =(tr[k<<1].val +tr[k<<1|1].val )%mod;
tr[k].val2=(tr[k<<1].val2+tr[k<<1|1].val2)%mod;
tr[k].val3=(tr[k<<1].val3+tr[k<<1|1].val3)%mod;
}
void eval(int k,int mul,int add)//子节点，父节点mul,add
{
int l=tr[k].l,r=tr[k].r;
tr[k].val3=((((mul%mod*mul%mod*mul%mod*tr[k].val3%mod
+add%mod*add%mod*add%mod*(r-l+1)%mod)%mod
+3*add%mod*mul%mod*mul%mod*tr[k].val2%mod)%mod
+3*add%mod*add%mod*mul%mod*tr[k].val)%mod)%mod;
tr[k].val2=(((mul%mod*mul%mod*tr[k].val2%mod+
2*add%mod*mul%mod*tr[k].val%mod)%mod)%mod
+(r-l+1)*add%mod*add%mod)%mod;
tr[k].val=(tr[k].val*mul%mod+(r-l+1)*add%mod)%mod;
tr[k].mul=(tr[k].mul*mul)%mod;
tr[k].add=(tr[k].add*mul%mod+add)%mod;
}
void push_down(int k,int l,int r)
{
if(tr[k].mul!=1||tr[k].add)
{
eval(k<<1,tr[k].mul,tr[k].add);
eval(k<<1|1,tr[k].mul,tr[k].add);
tr[k].add=0,tr[k].mul=1;
}
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r,tr[k].mul=1;
tr[k].val=tr[k].val2=tr[k].val3=tr[k].add=0;//多组数据
if(l==r)return;
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int x,int y,int mul,int add)
{
if(x<=l&&y>=r)
{
eval(k,mul,add);
return;
}
push_down(k,l,r);
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,y,mul,add);
if(y>=mid+1)modify(k<<1|1,mid+1,r,x,y,mul,add);
push_up(k);
}
int query(int k,int l,int r,int x,int y,int p)
{
if(x<=l&&y>=r)
{
if(p==1)return tr[k].val;
else if(p==2)return tr[k].val2;
else return tr[k].val3;
}
push_down(k,l,r);
int mid=l+r>>1;
int res=0;
if(x<=mid)res=query(k<<1,l,mid,x,y,p);
if(y>=mid+1)res=(res+ query(k<<1|1,mid+1,r,x,y,p))%mod;
return res%mod;
}
void solve(int _)
{
while(cin>>n>>m,n&&m)
{
build(1,1,n);
while(m--)
{
int op,l,r,c;
cin>>op>>l>>r>>c;
if(op==1)modify(1,1,n,l,r,1,c);
else if(op==2)modify(1,1,n,l,r,c,0);
else if(op==3)modify(1,1,n,l,r,0,c);
else cout<<query(1,1,n,l,r,c)<<endl;
}
}
}
signed main()
{
io;
int _;_=1;
//cin>>_;
rep(i,1,_)solve(i);
return 0;
}
求并集面积
const int N=100010;
int n;
struct snode
{
double x,y1,y2;
int v;
}seg[N<<1];//每个矩形两条竖线
struct node
{
int l,r;
int cnt;
double len;
}tr[N<<3];
vector<double>v;
int m;
int find(double x)
{
int l=1,r=v.size();
while(l<r)
{
int mid=l+r>>1;
if(v[mid]>=x)r=mid;
else l=mid+1;
}
return r;
}
void push_up(int k)
{
if(tr[k].cnt)tr[k].len=v[tr[k].r+1]-v[tr[k].l];//整段需要算len
else if(tr[k].cnt==0&&tr[k].l!=tr[k].r)//部分覆盖,未覆盖
tr[k].len=tr[k<<1].len+tr[k<<1|1].len;
else tr[k].len=0;//叶子节点
}
void build(int k,int l,int r)
{
tr[k].l=l,tr[k].r=r,tr[k].cnt=tr[k].len=0;
if(l==r)return;
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
push_up(k);
}
void modify(int k,int l,int r,int x,int y,int val)
{
if(x<=l&&y>=r)
{
tr[k].cnt+=val;
push_up(k);
return;
}
int mid=l+r>>1;
if(x<=mid)modify(k<<1,l,mid,x,y,val);
if(y>=mid+1)modify(k<<1|1,mid+1,r,x,y,val);
push_up(k);
}
void solve(int o)
{
int _=1;
while(cin>>n,n)
{
cout<<"Test case #"<<_++<<endl;
cout<<"Total explored area: ";
v.clear();
v.pb(-1e9);
for(int i=1,j=0;i<=n;i++)
{
double x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
seg[++j]={
x1,y1,y2,1};
seg[++j]={
x2,y1,y2,-1};
v.pb(y1),v.pb(y2);
}
sort(all(v));
n*=2;
v.erase(unique(all(v)),v.end());
m=v.size()-1;
build(1,1,m-1);//n的点，n-1个线段
sort(seg+1,seg+n+1,[&](snode a,snode b){
return a.x<b.x;
});
double res=0;
rep(i,1,n)
{
if(i!=1)res+=tr[1].len*(seg[i].x-seg[i-1].x);
modify(1,1,m-1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].v);
}
cout<<fixed<<setprecision(2)<<res<<endl;
cout<<endl;
}
}
珂朵莉树 [l,r]范围中的数字变成同一个
const int mod=1e9+7;
const int N=1e5+10;
int n,m,seed,maxv;
int a[N];
struct odt_node
{
int l,r;//l 和 r表示这一段的起点和终点
mutable int val;//表示这一段所有元素相同的值是多少
//mutable 即使是个常量，也允许修改值
odt_node(int l,int r=0,int val=0):l(l),r(r),val(val){
}
bool operator<(const odt_node &a)const{
return l<a.l;//规定按照每段的左端点进行排序
}
};
set<odt_node>odt;
int rnd()
{
int ret=seed;
seed=(seed*7ll+13ll)%mod;
return ret;
}
auto split(int x)//将一个包含x的区间[l,r]分裂成[l,x-1][x,r]
{
auto it=odt.lower_bound(odt_node(x));
if(it!=odt.end()&&it->l==x)return it;
--it;
if(it->r<x)return odt.end();
int l=it->l,r=it->r,val=it->val;
odt.erase(it);
odt.insert(odt_node(l,x-1,val));
return odt.insert(odt_node(x,r,val)).first;
}
void assign(int l,int r,int val)//推平操作。将[l,r]之间的区间干掉，然后替换一个完整的[l,r]
{
auto itr=split(r+1),itl=split(l);//一定先右，再左，否则RE
odt.erase(itl,itr);
odt.insert(odt_node(l,r,val));
}
void merge()//把元素相同的相邻的区间合并
{
if(odt.size()<=1)return;
set<odt_node>S;
for(auto it=odt.begin(),j=odt.begin();it!=odt.end();it++)
{
auto pre=it;
j=it;
bool f=false;
while(it!=odt.end()&&j->val==it->val)
{
if(f)pre++;
f=true;
it++;
}
S.insert(odt_node(j->l,pre->r,j->val));
it=pre;
}
odt=S;
}
void modify(int l,int r,int val)//区间修改，每个区间加上x
{
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
{
it->val+=val;
}
}
struct rnk
{
int num,cnt;
bool operator<(const rnk &a)const{
return num<a.num;
}
rnk(int num,int cnt):num(num),cnt(cnt){
}
};
int Rank(int l,int r,int k)//区间第k 小
{
vector<rnk>v;
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
v.pb(rnk(it->val,it->r - it->l + 1));
sort(all(v));
for(auto x:v)
{
k-=x.cnt;
if(k<=0)return x.num;
}
return -1;//找不到
}
void flip(int l,int r)//区间取反
{
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
{
it->val^=1;
}
}
int sum(int l,int r,int ex,int mod)
{
auto itr=split(r+1),itl=split(l);
int res=0;
for(auto it=itl;it!=itr;it++)
{
res=(res+(it->r-it->l+1)*qmi(it->val,ex,mod)%mod)%mod;
}
return res;
}
void read()
{
cin>>n>>m>>seed>>maxv;
rep(i,1,n)
{
a[i]=(rnd()%maxv)+1;
odt.insert(odt_node(i,i,a[i]));//刚开始自己一段
}
odt.insert(odt_node(n+1,n+1,0));//一定要加上！！！
//一定要加上！！！
//一定要加上！！！
//一定要加上！！！ 否则RE
}
void solve()
{
read();
rep(i,1,m)
{
int op=(rnd()%4)+1;
int l=(rnd()%n)+1;
int r=(rnd()%n)+1;
if(l>r)swap(l,r);
int x,y;
if(op==3)x=(rnd()%(r-l+1))+1;
else x=(rnd()%maxv)+1;
if(op==4)y=(rnd()%maxv)+1;
if(op==1)modify(l,r,x);
else if(op==2)assign(l,r,x);
else if(op==3)cout<<Rank(l,r,x)<<endl;
else cout<<sum(l,r,x,y)<<endl;
}
}
动态区间合并
void add(int left, int right)
{
// 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算）
for (auto it = mp.lower_bound(left); it != mp.end() && it->second <= right;) {
int l = it->second, r = it->first;
left = min(left, l); // 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值
right = max(right, r); // 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值
it=mp.erase(it);
}
mp[right] = left; // 所有被覆盖到的区间与 [left,right] 合并成一个新区间
}
文章评论