【数据结构】线段树复杂应用

1.线段树+离散化

逆序对

1.1逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i < j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 $n$ ，表示序列中有 $n$ 个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$ 。

输出格式

输出序列中逆序对的数目。

样例 #1

样例输入 #1

6
5 4 2 6 3 1

样例输出 #1

提示

对于 $25\%$ 的数据， $\leq 2500$

对于 $50\%$ 的数据， $\leq 4 \times 10^4$ 。

对于所有数据， $\leq 5 \times 10^5$

请使用较快的输入输出

应该不会 $O(n^2)$ 过 50 万吧 by chen_zhe

请对每一个你所学的知识保持一种尊敬的态度，千万不要说一个东西简单，是知识总会有他独特的价值，这也是为什么我要坚持写博客的一个原因！！！
题目传送门

不得不说今天晚上听了一下大佬讲解的逆序对，确实感觉这个东西非常的神奇，因为我发现这个东西不仅仅是一个归并排序那么简单的东西，实际上背后还大有学问，虽然本人并没有学会这道题的基本解决方式，但是跟着大佬混总还是会学到一些东西的，那么今天我就来为大家介绍一下离散化与动态开点

在开始之前还是先允许我先介绍一下这道题大致的解题思路，方便引入我们今天的主题。

首先朴素算法是这样的，我们先从第一个数开始一直到最后一个数，然后每次循环它前面的数，然后发现比它大的就记录下来（cnt++），然后我们就会发现会非常的爆炸，因为这样子的话，复杂度O(n^2)，400002……我不在多说了。

下面说一说比较正常的做法，相信大家都学过桶排序吧！这道题比较正常的做法是这样的，我们边读边处理，不对不对，应该是我们先做好了排序后再来进行一个一个处理，首先我们搞一个线段树，然后树中放的全部都是桶，是的，你没有看错，就是桶，统计这个数以来出现了多少次，那么你可能就会有所感觉了，这道题不就是，每次进行一次单点修改，区间求和的线段树吗?对的，你能想到这一点，我忠心祝贺你！的确是这样，我们每一次加入一个数，然后对他后面区间进行求值，就求到它的逆序对了。对对对，但是你如果能够想到博主想到这个方法的一定是一个SB，那么你就更厉害了。数据范围不是1e9吗！！！我靠，1e9个桶，直接树都开炸！对啊对啊，所以这个时候，离散化大法要出场了。

离散化（李三花）
小蓝居然可以把离散化读成那个，我觉得它非常的厉害！！！！！

话不多说，开始我们的离散化吧！其实大家完全没有必要去看网上那些东西，特别是百度百科，简直有毒，我们现在还用不到那么牛逼的离散化，所以这里介绍的离散化是非常简单的一种。

所谓离散化，就是说你发现了这个逆序对这道题啊，非常的讨厌，数据这么大，那么我们可不可以适当的把数据范围缩小一点呢？其实是可以的，我们发现，逆序对这道题有一个特点，就是比如说数据2 1还是数据 203903123 1它都是一个逆序对，前面的数都是比1大，但是我们不用管他比1大多少，只要比1大就可以了，但是为我们可以明显感觉到我们要对后面的数据处理一下，否则就要开爆树，在这里我们只需要把它处理成2就可以达到相同的效果。

举例一下：

2 33423434 437834 25345 373 35 //就可以被换成
1 6 5 4 3 2 //效果一样
但是你可能会说哎呦，我还排个序，编个号，那个时候我怎么知道原来它是什么样子的啊？

结构体大法好！！！

离散化基本操作如下：

#include<bits/stdc++.h>
using namespace std;
struct sd{int val,loc;//val是值 loc是当前点的位置 
}x[100005]; 
bool cmp(sd a,sd b)
{if(a.val<b.val)return true;
}
int discretization[100005];//这单词真够长 
int main()
{std::ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;++i){cin>>x[i].val;x[i].loc=i;}sort(x+1,x+n+1,cmp);int cnt=0; x[0].val=891881292;//important!for(int i=1;i<=n;++i){if(x[i-1].val==x[i].val)discretization[x[i].loc]=cnt;else {cnt++;discretization[x[i].loc]=cnt;}} for(int i=1;i<=n;++i){cout<<discretization[i]<<" ";}return 0;
}

打important的地方一定要注意，否则就要出事情！！！你想一想，如果我们呢第一个数为0那么那个cnt标记就不会++了！！！，恐怖！！！???

所以说我们离散化部分就讲完了，相信这道题你也应该可以A了。

标程代码：

#include<bits/stdc++.h>
#define ls(k) a[k].ch[0]
#define rs(k) a[k].ch[1]
using namespace std;
struct node { int l,r,cnt,ch[2];
};node a[510000];
int cnt=1;
struct num { int val;int loc;bool operator < (const num &a) const { return val<a.val;} 
};
num lisanhua[51000];
int yingshe[51000];
int n;
void init() { int cnt=0;cin>>n;for(int i=1;i<=n;++i) { cin>>lisanhua[i].val;lisanhua[i].loc=i;} sort(lisanhua+1,lisanhua+n+1);lisanhua[0].val=19260817;for(int i=1;i<=n;++i){if(lisanhua[i].val!=lisanhua[i-1].val) yingshe[lisanhua[i].loc]=cnt+1,++cnt;else yingshe[lisanhua[i].loc]=cnt;}
} void update(int k) { a[k].cnt=a[ls(k)].cnt+a[rs(k)].cnt;
} void build(int k,int l,int r) { a[k].l=l;a[k].r=r;if(l==r) return;int mid=l+r;mid/=2;ls(k)=cnt+1,++cnt,build(cnt,l,mid);rs(k)=cnt+1,++cnt,build(cnt,mid+1,r);
} void ins(int k,int val) { if(a[k].l==a[k].r&&a[k].l==val) { a[k].cnt++;return;} int mid=a[k].l+a[k].r;mid/=2;if(val<=mid) ins(ls(k),val);else ins(rs(k),val);update(k);
} int query(int k,int l,int r) { if(a[k].l==l&&a[k].r==r) { return a[k].cnt;} int mid=a[k].l+a[k].r;mid/=2;if(r<=mid) return query(ls(k),l,r);else if(l>mid) return query(rs(k),l,r);else return query(ls(k),l,mid)+query(rs(k),mid+1,r);
} void prit(int k) { printf("%d %d %d %d %d %d\n",k,ls(k),rs(k),a[k].l,a[k].r,a[k].cnt);if(ls(k)!=0) prit(ls(k));if(rs(k)!=0) prit(rs(k));
} int main() { build(1,0,51000);init();long long ans=0;for(int i=1;i<=n;++i) { ins(1,yingshe[i]);ans+=query(1,yingshe[i]+1,n+1);} cout<<ans;return 0;
}

技巧：这里我们使用了先建树（空树）然后在modify的的写法，希望大家能够理解一下！
好了，就这样了，但是如果哪一天你就是说，哎呀这个离散化写着太让我烦恼了，那么有没有另外一种写法呢？很明显是有的，那么就是我们的动态开点了，这样子写有一个好处，就是我们不用写Buildtree啦！是不是听起来很爽呢？我们每次在push的时候就顺便把它的儿子女儿都建了，具体过程不在赘述，这里就贴一段动态开点建树的代码过程，其实大家只要认真的把代码看懂了，那么你就已经掌握到了动态开点建树的精髓了（用了动态开点就可以不用离散化了哟！！）！！！！！！

代码如下：

void modify(int k,int val)
{if(node[k].l==node[k].r&&node[k].l==val){node[k].cnt++;return;}int mid=node[k].l+node[k].r;mid/=2;if(node[k].son[0]==0){cnt++;node[k].son[0]=cnt;node[cnt].l=node[k].l;node[cnt].r=mid;}if(node[k].son[1]==0){cnt++;node[k].son[1]=cnt;node[cnt].l=mid+1;node[cnt].r=node[k].r;}if(val>mid){modify(node[k].son[1],val);}else{modify(node[k].son[0],val);}update(k);
}

这只是征程的开始，线段树的精髓远远不止这些！！！

标程代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
struct sd{int son[2];long long l,r,cnt;
}node[N];
int n;
int cnt=1;
long long ans;
void update(int k)
{node[k].cnt=node[node[k].son[0]].cnt+node[node[k].son[1]].cnt;
}
void modify(int k,int val)
{if(node[k].l==node[k].r&&node[k].l==val){node[k].cnt++;return;}int mid=node[k].l+node[k].r;mid/=2;if(node[k].son[0]==0){cnt++;node[k].son[0]=cnt;node[cnt].l=node[k].l;node[cnt].r=mid;}if(node[k].son[1]==0){cnt++;node[k].son[1]=cnt;node[cnt].l=mid+1;node[cnt].r=node[k].r;}if(val>mid){modify(node[k].son[1],val);}else{modify(node[k].son[0],val);}update(k);
}
long long query(int k,int ql,int qr)
{if(k==0) return 0;//very very important！！！if(node[k].l==ql&&node[k].r==qr){return node[k].cnt;}else{int mid=(node[k].l+node[k].r)/2;if(qr<=mid) return query(node[k].son[0],ql,qr);else if(ql>mid) return query(node[k].son[1],ql,qr);else{return query(node[k].son[0],ql,mid)+query(node[k].son[1],mid+1,qr);}}
}
int main()
{std::ios::sync_with_stdio(false);node[1].l=1; node[1].r=1e9+7;int n,sth;cin>>n;ans=0;for(int i=1;i<=n;++i){cin>>sth;modify(1,sth);ans+=query(1,sth+1,1e9+7);}cout<<ans<<endl;
}

关于动态开点的注意事项，我后面在写吧！！！

于是我履行了诺言，下面就是动态开点最为重要的一个注意事项！！

大家认真的阅读一下代码，可以发现我在代码中加入了一个very very important 的标记，这里一定要写这句话，为什么呢？因为我们动态开点，开到叶节点的时候一定会遇到一种情况，就是叶节点并没有儿子，那么他的儿子编号就是0，所以在下一次递归中就会递归到0号节点，然后0号什么参数都是0，于是程序开始原地转圈，然后就爆炸了！！！！其实这道题写不写都可以，但是这里只是做一个小小的提醒！！！

这只是征程的开始，线段树的精髓远远不止这些！！！ By njc

point

1.2Points

题面翻译

在一个笛卡尔坐标系中，定义三种操作:

add x y :在坐标系上标记一个点 $(x, y)$ ，保证 $(x, y)$ 在添加前不在坐标系上。
remove x y :移除点 $(x, y)$ ，保证 $(x, y)$ 在移除前已在坐标系上。
find x y :找到所有已标记并在 $(x, y)$ 右上方的点中，最左边的点，若点不唯一，选择最下面的一个点; 如果没有符合要求的点，给出 -1，否则给出 $(x, y)$ 。

现有 $n$ 个操作,对于每个 find 操作，输出结果。

$\le 2 \times 10^5$ ， $\le x,y \le 10^9$ 。

题目描述

Pete and Bob invented a new interesting game. Bob takes a sheet of paper and locates a Cartesian coordinate system on it as follows: point $ (0,0) $ is located in the bottom-left corner, $ Ox $ axis is directed right, $ Oy $ axis is directed up. Pete gives Bob requests of three types:

add x y — on the sheet of paper Bob marks a point with coordinates $ (x,y) $ . For each request of this type it’s guaranteed that point $ (x,y) $ is not yet marked on Bob’s sheet at the time of the request.
remove x y — on the sheet of paper Bob erases the previously marked point with coordinates $ (x,y) $ . For each request of this type it’s guaranteed that point $ (x,y) $ is already marked on Bob’s sheet at the time of the request.
find x y — on the sheet of paper Bob finds all the marked points, lying strictly above and strictly to the right of point $ (x,y) $ . Among these points Bob chooses the leftmost one, if it is not unique, he chooses the bottommost one, and gives its coordinates to Pete.

Bob managed to answer the requests, when they were 10, 100 or 1000, but when their amount grew up to $ 2·10^{5} $ , Bob failed to cope. Now he needs a program that will answer all Pete’s requests. Help Bob, please!

输入格式

The first input line contains number $ n $ ( $ 1<=n<=2·10^{5} $ ) — amount of requests. Then there follow $ n $ lines — descriptions of the requests. add x y describes the request to add a point, remove x y — the request to erase a point, find x y — the request to find the bottom-left point. All the coordinates in the input file are non-negative and don’t exceed $ 10^{9} $ .

输出格式

For each request of type find x y output in a separate line the answer to it — coordinates of the bottommost among the leftmost marked points, lying strictly above and to the right of point $ (x,y) $ . If there are no points strictly above and to the right of point $ (x,y) $ , output -1.

样例 #1

样例输入 #1

7
add 1 1
add 3 4
find 0 0
remove 1 1
find 0 0
add 1 1
find 0 0

样例输出 #1

1 1
3 4
1 1

样例 #2

样例输入 #2

13
add 5 5
add 5 6
add 5 7
add 6 5
add 6 6
add 6 7
add 7 5
add 7 6
add 7 7
find 6 6
remove 7 7
find 6 6
find 4 4

样例输出 #2

7 7
-1
5 5

Problem
题目已经说的很清楚了，只不过还有要注意的就是这个“右上方”指的是严格大于，也就是
x
1

x
2
x
1

x
2

，
y
1

y
2
y
1

y
2

。

Solution
首先看到值域的数据范围我们可以想到先离散化一下。

然后我们考虑用线段树维护横坐标为
1
,
2
,
3
,
4…
1,2,3,4… 时的纵坐标最大值。（也就是每一个横坐标上的最大纵坐标，在这个基础上线段树维护最大值。）

对于每一个横坐标可以开一个 set 维护这个坐标内部的点。

那么题目上的操作就很好实现了，添加操作就是先看看可不可以取代当前的那个位置上的最大值，然后再插入进 set 里。

删除操作就是先在对应横坐标的 set 里删除，然后再用当前 set 里的最大值放进线段树里，覆盖掉原来的那个。

最后查找操作就是先在线段树上二分，找到最左边的，且横坐标大于
x
x ，值大于
y
y 的位置。

（注意这里的值指的是线段树维护的那个 Max ，因为我们这里只是看在这个坐标上有没有解，至于题目要求的还要
y
y 尽可能小，我们一会先定位横坐标，再在这个横坐标的 set 上找。）

于是我们再在这个位置上的 set 当中二分找到第一个大于
y
y 的值，再映射回原数组（因为离散化了的），就是答案了。

Code

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){x=0;char ch=getchar();bool f=false;while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=f?-x:x;return ;
}
template <typename T>
inline void write(T x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10^48);return ;
}
const int N=4e5+5; 
#define ll long long
struct Query{int op,x,y;}Q[N];
int n,m,b[N],cnt,Max[N<<2];
set<int> ST[N];
void Pushup(int x){Max[x]=max(Max[x<<1],Max[x<<1|1]);return ;}
void Modify(int x,int l,int r,int pos,int v){if(l==r){Max[x]=max(Max[x],v);return ;}int mid=l+r>>1;if(pos<=mid) Modify(x<<1,l,mid,pos,v);else Modify(x<<1|1,mid+1,r,pos,v);Pushup(x);return ;
} 
void Change(int x,int l,int r,int pos,int v){if(l==r){Max[x]=v;return ;}int mid=l+r>>1;if(pos<=mid) Change(x<<1,l,mid,pos,v);else Change(x<<1|1,mid+1,r,pos,v);Pushup(x);return ;
} 
int QueryPos(int x,int l,int r,int X,int Y){if(l==r){if(Max[x]>Y) return l;return -1;}int mid=l+r>>1,res=-1;if(X<=mid&&Max[x<<1]>Y) res=QueryPos(x<<1,l,mid,X,Y);if(~res) return res;if(Max[x<<1|1]>Y) return QueryPos(x<<1|1,mid+1,r,X,Y); return -1;
}
int main(){read(n);for(int i=1;i<=n;i++){char op[10];int x,y;scanf("%s",op);read(x),read(y);if(op[0]=='a') Q[i].op=1,Q[i].x=x,Q[i].y=y; else if(op[0]=='r') Q[i].op=2,Q[i].x=x,Q[i].y=y; else Q[i].op=3,Q[i].x=x,Q[i].y=y; b[++cnt]=x,b[++cnt]=y;}sort(b+1,b+cnt+1);int idx=unique(b+1,b+cnt+1)-b-1;for(int i=1;i<=n;i++) Q[i].x=lower_bound(b+1,b+idx+1,Q[i].x)-b,Q[i].y=lower_bound(b+1,b+idx+1,Q[i].y)-b;for(int i=1;i<=n;i++){if(Q[i].op==1) ST[Q[i].x].insert(Q[i].y),Modify(1,1,idx,Q[i].x,Q[i].y);else if(Q[i].op==2){ST[Q[i].x].erase(ST[Q[i].x].find(Q[i].y));if(ST[Q[i].x].empty()){Change(1,1,idx,Q[i].x,0);continue;}Change(1,1,idx,Q[i].x,*ST[Q[i].x].rbegin());}else{int Pos=QueryPos(1,1,idx,Q[i].x+1,Q[i].y);if(Pos==-1) puts("-1");else write(b[Pos]),putchar(' '),write(b[*ST[Pos].upper_bound(Q[i].y)]),putchar('\n');}}return 0;
}

在这里插入图片描述

Code：

#include<cstdio>
#include<algorithm>
#include<set> 
#include<vector>
#define N 200005
struct istream{template<typename T>inline istream&operator>>(T&d){static int c;while(!isdigit(c=getchar()));for(d=0;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');return*this;}
}cin;
int n;
std::vector<int>X,Y;
struct cmd{char opt[7];int x,y;
}q[N];
int d[N<<2];
std::set<int>b[N]; 
void modify(int l,int r,int o,const int&pos,const int&ch){if(l==r)d[o]=ch;else{const int mid=l+r>>1;if(pos<=mid)modify(l,mid,o<<1,pos,ch);elsemodify(mid+1,r,o<<1|1,pos,ch);d[o]=std::max(d[o<<1],d[o<<1|1]);}
}
void query(int l,int r,int o,const int&X,const int&Y,int&x){if(l==r){if(d[o]>=Y)x=l;return;}const int mid=l+r>>1;if(X<=mid&&d[o<<1]>=Y)query(l,mid,o<<1,X,Y,x);if(~x)return;if(d[o<<1|1]>=Y)query(mid+1,r,o<<1|1,X,Y,x);
}
void build(int l,int r,int o){d[o]=-1;if(l<r){const int mid=l+r>>1;build(l,mid,o<<1),build(mid+1,r,o<<1|1);}
}
int main(){X.push_back(-1),Y.push_back(-1);cin>>n;build(1,n,1);for(int i=1;i<=n;++i){scanf("%s",q[i].opt);cin>>q[i].x>>q[i].y;if(*q[i].opt=='f')++q[i].x,++q[i].y;X.push_back(q[i].x),Y.push_back(q[i].y);b[i].insert(-1);}std::sort(X.begin(),X.end());std::sort(Y.begin(),Y.end());X.erase(std::unique(X.begin(),X.end()),X.end());Y.erase(std::unique(Y.begin(),Y.end()),Y.end());for(int i=1;i<=n;++i){q[i].x=std::lower_bound(X.begin(),X.end(),q[i].x)-X.begin();q[i].y=std::lower_bound(Y.begin(),Y.end(),q[i].y)-Y.begin();if(*q[i].opt=='a'){int mx=*b[q[i].x].rbegin();if(mx<q[i].y)modify(1,n,1,q[i].x,q[i].y);b[q[i].x].insert(q[i].y);}elseif(*q[i].opt=='r'){b[q[i].x].erase(b[q[i].x].find(q[i].y));modify(1,n,1,q[i].x,*b[q[i].x].rbegin());}else{int x=-1;query(1,n,1,q[i].x,q[i].y,x);if(x==-1)puts("-1");elseprintf("%d %d\n",X[x],Y[*b[x].lower_bound(q[i].y)]);}}return 0;
}

星际旅行（就是那个xs[r]-xs[l-1]）单独打了一篇

一篇很好的题解
前置知识
线段树：通过懒惰标记，可实现区间处理，和区间询问皆为
在这里插入图片描述

#include <bits/stdc++.h>#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1//左子树，st*2
#define rs st<<1|1//右子树，st*2+1
using namespace std;
const int maxn = (ll) 4e5 + 5;
const int mod = 1e9 + 7;
int T = 1;
vector<int> v;
struct node {int lazS, lazM, sum;
} t[3][maxn << 3];
int lazC[maxn << 3];
int len[maxn << 3];
int q[maxn][6];void build(int st, int l, int r) {for (int i = 0; i <= 2; ++i)t[i][st].lazM = 1;/** 最右区间长度为0* 由于保留左闭右开区间，所以长度为v[l + 1] - v[l]*/if (l == r) {if (l == v.size() - 1)len[st] = 0;elselen[st] = v[l + 1] - v[l];return;}int mid = (l + r) >> 1;build(ls, l, mid);build(rs, mid + 1, r);len[st] = len[ls] + len[rs];
}void change(int rt, int st) {if (lazC[rt] == 1) {//向左平移一维node x = t[0][st], y = t[1][st], z = t[2][st];t[0][st] = y;t[1][st] = z;t[2][st] = x;} else if (lazC[rt] == 2) {//向左平移两维node x = t[0][st], y = t[1][st], z = t[2][st];t[0][st] = z;t[1][st] = x;t[2][st] = y;}
}void push_down(int st) {if (lazC[st]) {//先进行转换操作change(st, ls);change(st, rs);lazC[ls] = (lazC[ls] + lazC[st]) % 3;lazC[rs] = (lazC[rs] + lazC[st]) % 3;lazC[st] = 0;}for (int i = 0; i <= 2; ++i) {t[i][ls].sum = ((t[i][ls].sum * t[i][st].lazM) % mod + t[i][st].lazS * len[ls]) % mod;//先进行乘法操作，再进行加法操作t[i][rs].sum = ((t[i][rs].sum * t[i][st].lazM) % mod + t[i][st].lazS * len[rs]) % mod;//先进行乘法操作，再进行加法操作t[i][ls].lazS = ((t[i][ls].lazS * t[i][st].lazM) % mod + t[i][st].lazS) % mod;//注意加法标记要先做乘法，再做加法t[i][rs].lazS = ((t[i][rs].lazS * t[i][st].lazM) % mod + t[i][st].lazS) % mod;//注意加法标记要先做乘法，再做加法t[i][ls].lazM = t[i][ls].lazM * t[i][st].lazM % mod;//乘法标记直接操作即可t[i][rs].lazM = t[i][rs].lazM * t[i][st].lazM % mod;//乘法标记直接操作即可t[i][st].lazM = 1;//清除懒惰标记t[i][st].lazS = 0;//清除懒惰标记}
}void add(int st, int l, int r, int L, int R, int a[]) {if (L <= l && r <= R) {for (int i = 0; i <= 2; ++i) {t[i][st].lazS = (t[i][st].lazS + a[i]) % mod;t[i][st].sum = (t[i][st].sum + a[i] * len[st]) % mod;//注意lazS保留的仅仅是加法，以便对于不同区间根据长度判定加和}return;}push_down(st);int mid = (l + r) >> 1;if (L <= mid)add(ls, l, mid, L, R, a);if (R > mid)add(rs, mid + 1, r, L, R, a);for (int i = 0; i <= 2; ++i)t[i][st].sum = (t[i][ls].sum + t[i][rs].sum) % mod;
}void mul(int st, int l, int r, int L, int R, int val) {if (L <= l && r <= R) {for (int i = 0; i <= 2; ++i) {t[i][st].sum = (t[i][st].sum * val) % mod;t[i][st].lazM = (t[i][st].lazM * val) % mod;t[i][st].lazS = (t[i][st].lazS * val) % mod;//由乘法分配律，lazS也需要乘}return;}push_down(st);int mid = (l + r) >> 1;if (L <= mid)mul(ls, l, mid, L, R, val);if (R > mid)mul(rs, mid + 1, r, L, R, val);for (int i = 0; i <= 2; ++i)t[i][st].sum = (t[i][ls].sum + t[i][rs].sum) % mod;
}void change(int st, int l, int r, int L, int R) {if (L <= l && r <= R) {lazC[st] = (lazC[st] + 1) % 3;//转换操作转换三次后就等于不转换，所以取模node x = t[0][st], y = t[1][st], z = t[2][st];//lazC标记实际含义为保留子节点的信息，所以父节点要进行操作t[0][st] = y;t[1][st] = z;t[2][st] = x;return;}push_down(st);int mid = (l + r) >> 1;if (L <= mid)change(ls, l, mid, L, R);if (R > mid)change(rs, mid + 1, r, L, R);for (int i = 0; i <= 2; ++i)t[i][st].sum = (t[i][ls].sum + t[i][rs].sum) % mod;
}void query(int st, int l, int r, int L, int R, int a[]) {if (L <= l && r <= R) {for (int i = 0; i <= 2; ++i) {a[i] = (a[i] + t[i][st].sum) % mod;}return;}push_down(st);int mid = (l + r) >> 1;if (L <= mid)query(ls, l, mid, L, R, a);if (R > mid)query(rs, mid + 1, r, L, R, a);
}void solve() {//注意本代码已#define int long longint n, m;cin >> n >> m;//为离散化，先读入，后操作for (int i = 1; i <= m; ++i) {cin >> q[i][0] >> q[i][1] >> q[i][2];++q[i][2];//形成左闭右开区间v.push_back(q[i][1]);v.push_back(q[i][2]);if (q[i][0] == 1) {for (int j = 3; j <= 5; ++j)cin >> q[i][j];} else if (q[i][0] == 2) {cin >> q[i][3];}}v.push_back(LLONG_MIN);//放入一个最小值，保证数组以1开始，也可以开一个数组进行离散化sort(v.begin(), v.end());//离散化需要先排序v.erase(unique(v.begin(), v.end()), v.end());//将多余的数字去除for (int i = 1; i <= m; ++i) {//通过二分离散化q[i][1] = lower_bound(v.begin(), v.end(), q[i][1]) - v.begin();q[i][2] = lower_bound(v.begin(), v.end(), q[i][2]) - v.begin();}int tot = v.size() - 1;//线段树的叶子结点个数，即操作区间的最右端点build(1, 1, tot);for (int i = 1; i <= m; ++i) {//由于操作左闭右开区间，所以每次操作右端点需要-1if (q[i][0] == 1) {int x[] = {q[i][3], q[i][4], q[i][5]};add(1, 1, tot, q[i][1], q[i][2] - 1, x);} else if (q[i][0] == 2) {mul(1, 1, tot, q[i][1], q[i][2] - 1, q[i][3]);} else if (q[i][0] == 3) {change(1, 1, tot, q[i][1], q[i][2] - 1);} else {int x[] = {0, 0, 0};query(1, 1, tot, q[i][1], q[i][2] - 1, x);int ans = 0;for (int j = 0; j <= 2; ++j) {ans = (ans + x[j] * x[j] % mod) % mod;}cout << ans << '\n';}}
}signed main() {start;//关同步while (T--)solve();return 0;
}

总结
本题难点在于三个标记的影响以及区间离散化。

对于前两个标记在洛谷OJ中有原题，转换则需要考虑多种组合，以及不正确转换的反例，比如说转换和运算的先后，是否带标记转换还是只转换
s
u
m
，转换根据本节点的标记还是父节点的标记等等。题解给出的是正确的转换方式，但是非正确的转换方式很容易干扰思路，所以请完全理解为什么如此转换。

而区间离散化首先需要理解离散化的思想，其次理解为什么要将区间变为左闭右开区间，最后理解每一个节点代表什么。

2.其他练习

2.1星际网络2

随着星际网络的进一步建设和规模的增大，一个新的问题出现在网络工程师面前——`地址空间不够用了！

原来，星际网络采用了传统的 IPv6 协议，虽然有 $2^{128}$ 级别的可用地址数量，但面对广袤无垠的宇宙和爆炸式增长的网络用户数，如此庞大的地址空间也面临了用尽的那一天。

新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。

最终，经过 $2333$ 年的不懈努力，西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”，又称 IPxxaf。

在 IPxxaf 协议中，一个地址由 $n$ 位二进制位组成，其中 $n$ 是 $16$ 的倍数。

日常表示一个地址时，采用类似 IPv6 协议的十六进制表示法，每 $4$ 位用 : 隔开。

如 $n = 32$ 时，地址为 2a00:0001，即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001 的地址。

注意不会出现 IPv6 中省略每组的前导 $0$ 或用 :: 省略一段 $0$ 的情况。

为方便起见，记 $n u m (s)$ 为地址 $s$ 按高位在前、低位在后组成的 $n$ 位二进制数，称一段“连续的地址“为 $n u m (s)$ 成一段连续区间的一系列地址。

西西艾弗星的网络管理员负责地址的分配与管理。

最开始，整个地址空间都是未分配的。

用户可以随时向管理员申请一些地址：

1 id l r：表示用户 $i d$ 申请地址在 $\sim r$ 范围内（包含 $l$ 和 $r$ ，下同）的一段连续地址块。

在地址申请操作中，管理员需要先检查地址是否可用。

如果用户申请的地址全部未被分配，则检查通过；若地址中存在已经分配给其他用户的地址，则检查失败。

但有一种特殊情况：申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。

此时可以认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。

如果上述检查通过，则管理员向用户返回 YES，并将申请的地址分配给该用户；若不通过，则向用户返回 NO，同时不改变现有的地址分配。

网络管理员要定期检查地址的分配情况，具体而言有如下两种操作：

2 s：检查地址 $s$ 被分配给了哪个用户。若未被分配，则结果为 $0$ 。

3 l r：检查 $\sim r$ 范围内的所有地址是否完整地分配给了某个用户。若是，回答该用户的编号；若否，回答 $0$ 。

在整个网络的运行过程中，共出现了 $q$ 次申请地址和检查地址分配的操作。

作为西西艾弗星的一名重要的网络技术顾问，你要帮网络管理员依次处理每个操作，并回答相应的结果。

输入格式

第一行， $2$ 个正整数 $n, q$ 。

接下来 $q$ 行，每行一个操作，格式如上所述，其中的 $i d$ 为正整数， $l, r, s$ 均为 IPxxaf 地址串，其中十六进制均用数字和小写字母表示。

输出格式

输出 $q$ 行，每行一个非负整数或字符串，表示此次操作的结果。

其中，对于操作 $1$ ，输出 YES 或 NO；对于操作 $2, 3$ ，输出一个非负整数。

数据范围

对于所有数据， $\le 512$ ， $\le 5 \times 10^4$ ， $n$ 为 $16$ 的倍数， $\le q$ ，对于操作 $1, 3$ 保证 $\le num(r)$ 。

测试点编号

$\le$

特殊性质

$\sim 4$

$16$

$200$

无

$\sim 6$

$64$

$200$

无

$\sim 9$

$512$

$200$

无

$\sim 11$

$16$

$20000$

无

$\sim 13$

$64$

$50000$

无

$\sim 16$

$512$

$50000$

所有操作 $1$ 的 $i d$ 互不相同

$\sim 20$

$512$

$50000$

无

输入样例：

32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff

输出样例：

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1

样例解释

第 $4$ 个操作时，由于用户 $2$ 申请的部分地址已被分配给用户 $1$ ，因此申请不通过；

第 $6$ 个操作时，由于用户 $1$ 申请的全部地址已被分配给用户 $1$ ，因此申请不通过；

第 $11$ 个操作时，用户 $1$ 申请的部分地址已被分配给用户 $1$ ，其余地址尚未被分配，申请通过；

样例输入：

32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff
样例输出：

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1
分析：这道题目算是一道线段树模板题了，线段树每个地址代表一个点，这个点的值就是这个地址分配给了哪个编号。我们需要维护的信息有最大值和最小值以及当前地址块已经有多少地址被分配(对应的就是区间和)。最大值初始化为-0x3f3f3f3f,最小值初始化为0x3f3f3f3f.

对于操作1：假如我们要分配给编号id的地址区间为[l,r]，那么我们先查询一下获得该区间内地址的编号的最大值是多少，如果最大值是-0x3f3f3f3f，说明这块地址还没有进行分配，那么可以直接进行区间修改把这块地址全部赋值为id。如果发现最大值不是-0x3f3f3f3f，说明这块地址已经存在部分被分配的情况，这个时候我们查一下最小值，如果最小值和最大值不相同，说明这块地址不仅是一个人占有，那么我们就无需进行操作，如果最小值和最大值相同，那么这块地址最多分配给了一个人，这个时候我们要检查一下是不是全部地址都分配给了这个人，这个时候就用区间和来查询，如果区间和等于区间长度，那么就说明这段地址空间全部分配给了一个人，直接返回失败就可以了，否则判断一下我们所查询的值与待分配编号是否相同即可，如果相同，那么说明还有部分地址是空着的，那么我们直接把整个区间的值全部赋值为id即可，否则就是无法继续分配。

对于操作2：就对应一个单点查询操作，如果查询出来为空就输出0，否则输出查询出的id即可。

对于操作3：这个是类似于操作1的，因为操作1是在检查是否完整分配给某个用户的基础上决定是否能够继续分配的，所以操作3就是操作1的一个子操作，这里就不再叙述了。

但是需要注意的就是我们需要对所给定的地址区间边界进行离散化，要不然对于512位数字的可能组合我们是不可能全部记录下来的。但是离散化的时候需要注意，比如现在有两个区间[1,7]和[11,15]，这个时候我们不仅要加入1，7，11，15这四个数，我们还要把7和11之间的数选择一个加入，为什么呢？因为如果不加入，那么离散化后的结果就是1->1,7->2,11->3,15->4,假如我们现在已经把[1,7]和[11,15]这两个区间分配给了编号1，那么在离散后的结果上就相当于区间[1,2]和区间[3,4]都已经赋值1，那么我们下次假如想把区间[1,15]全部分配给1，按照题意理解我们可以发现这个操作是合法的因为实际上区间[8,10]属于未分配地址空间，这个时候我们可以把这些地址分配给编号1，但是我们在离散化后的线段树上查询发现区间[1,4]均已分配给编号1，那么就会返回分配失败的消息。但如果我们把每个操作区间右端点后面一个数也加进离散化数组，这个时候我们得到的离散化数组就是1->1,7->2,8->3,11->4,15->5,16->6.那么我们把[1,7]和[11,15]这两个区间分配给了编号1就相当于把区间[1,2]和区间[4,5]赋值为1，下次查询区间[1,15]相当于查询区间[1,5]，这个时候可以发现还是存在一些空地址的，这样就可以解决这个问题。

细节见代码：


#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e6+10;
int l[N],r[N],mx[N],mn[N],lz[N],s[N];
void pushup(int id)
{mx[id]=max(mx[id<<1],mx[id<<1|1]);mn[id]=min(mn[id<<1],mn[id<<1|1]);s[id]=s[id<<1]+s[id<<1|1];
}
void pushdown(int id)
{if(lz[id]!=0x3f3f3f3f){s[id<<1]=r[id<<1]-l[id<<1]+1;s[id<<1|1]=r[id<<1|1]-l[id<<1|1]+1;mx[id<<1]=lz[id];mx[id<<1|1]=lz[id];mn[id<<1]=lz[id];mn[id<<1|1]=lz[id];lz[id<<1]=lz[id];lz[id<<1|1]=lz[id];lz[id]=0x3f3f3f3f;}
}
void build(int id,int L,int R)
{l[id]=L;r[id]=R;mn[id]=0x3f3f3f3f;mx[id]=-0x3f3f3f3f;lz[id]=0x3f3f3f3f;if(L>=R) return ;int mid=L+R>>1;build(id<<1,L,mid);build(id<<1|1,mid+1,R);pushup(id);
}
void update_interval(int id,int L,int R,int val)
{if(l[id]>=L&&r[id]<=R){s[id]=r[id]-l[id]+1;mx[id]=val;mn[id]=val;lz[id]=val;return ;}pushdown(id);int mid=l[id]+r[id]>>1;if(mid>=L) update_interval(id<<1,L,R,val);if(mid+1<=R) update_interval(id<<1|1,L,R,val);pushup(id);
}
int query_mx(int id,int L,int R)
{if(l[id]>=L&&r[id]<=R) return mx[id];pushdown(id);int mid=l[id]+r[id]>>1;int ans=-0x3f3f3f3f;if(mid>=L) ans=query_mx(id<<1,L,R);if(mid+1<=R) ans=max(ans,query_mx(id<<1|1,L,R));return ans;
}
int query_mn(int id,int L,int R)
{if(l[id]>=L&&r[id]<=R) return mn[id];pushdown(id);int mid=l[id]+r[id]>>1;int ans=0x3f3f3f3f;if(mid>=L) ans=query_mn(id<<1,L,R);if(mid+1<=R) ans=min(ans,query_mn(id<<1|1,L,R));return ans;
}
int query_sum(int id,int L,int R)
{if(l[id]>=L&&r[id]<=R) return s[id];pushdown(id);int mid=l[id]+r[id]>>1;long long ans=0;if(mid>=L) ans+=query_sum(id<<1,L,R);if(mid+1<=R) ans+=query_sum(id<<1|1,L,R);return ans;
}
int n,q;
vector<string> alls;
string add(string s)
{int flag=1;string t=s;for(int i=s.size()-1;i>=0;i--){if(s[i]==':') continue;else if(s[i]=='f'&&flag)t[i]='0';else{if(s[i]=='9') t[i]='a';else t[i]=s[i]+1;break;}}return t;
}
int find(string s)
{return lower_bound(alls.begin(),alls.end(),s)-alls.begin()+1;
}
struct node{int op;int id;string l,r;
}p[N];
int main()
{cin>>n>>q;for(int i=1;i<=q;i++){scanf("%d",&p[i].op);if(p[i].op==1){cin>>p[i].id>>p[i].l>>p[i].r;alls.push_back(p[i].l);alls.push_back(p[i].r);alls.push_back(add(p[i].r));}else if(p[i].op==2){cin>>p[i].l;alls.push_back(p[i].l);}else{cin>>p[i].l>>p[i].r;alls.push_back(p[i].l);alls.push_back(p[i].r);alls.push_back(add(p[i].r));}}sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());build(1,1,alls.size());for(int i=1;i<=q;i++){if(p[i].op==1){int ll=find(p[i].l),rr=find(p[i].r);if(query_mn(1,ll,rr)==0x3f3f3f3f)//该块土地全部未被分配 {puts("YES");update_interval(1,ll,rr,p[i].id);}else if(query_mn(1,ll,rr)==p[i].id&&query_mx(1,ll,rr)==p[i].id)//该块土地只分配给了一个人 {if(query_sum(1,ll,rr)==(rr-ll+1))//该块土地本来就已经全部分配给了p[i].id puts("NO");else{puts("YES");update_interval(1,ll,rr,p[i].id);} }else//该块土地已经分配给了除了p[i].id以外的人，所以无法再分配给p[i].id puts("NO");}else if(p[i].op==2){int ll=find(p[i].l);int t=query_mx(1,ll,ll);if(t!=-0x3f3f3f3f)printf("%d\n",t);elseprintf("0\n");}else{int ll=find(p[i].l),rr=find(p[i].r);int id=query_mn(1,ll,rr);if(id==query_mx(1,ll,rr)&&query_sum(1,ll,rr)==(rr-ll+1))//该块土地只分配给了一个人 printf("%d\n",id);elseprintf("0\n");}}return 0;

PS无线版

ps无限版
众所周知，PS 是一款图片编辑软件，编辑图片的本质是操作各像素。

但是，传统的图片编辑只能对有限个像素进行操作，而这对于一名数学系学生是不可忍受的——竟然不能把有限的、离散的问题推广到无穷的、连续的问题，这真是不可忍受。

正如在线性代数的理论我们为了将有限维线性空间推广到无穷维线性空间所做的那样，现在我们可以假定一张图片是一个无穷大的二维平面（方便起见，我们假定它是一个平面直角坐标系），其上的每个像素可以用 (a,b)(a,b) 表示（注意，a,ba,b 是实数）。类似于线性代数无穷维线性空间关于基的讨论，我们实际上不关心所有的像素，而只关注于其中的有限个像素，通过对每一组有限大小的像素集的刻画来描述图片整体的编辑情况。

当然，尽管在原理上成功的把 PS 升级成了 PSI(PS Infinite)，但就结论而言，我们应当讨论传统 PS 中的各种操作在 PSI 上的推广和实现。出于简单起见，我们只考虑平移、旋转、放缩、对称和投影这些基本的编辑操作。

题目描述
给定正整数 nn 平面上一些点 (xi,yi)i=1n⊂ℜ2(xi,yi)i=1n⊂ℜ2，支持以下操作：

1 l r a b1 l r a b：将编号在 [l,r][l,r] 中的点平移 v⃗=(a,b)v=(a,b)。
即沿 v⃗v 方向平移 ∣v⃗∣∣v∣ 的距离。
2 l r a b θ2 l r a b θ：将编号在 [l,r][l,r] 中的点以 (a,b)(a,b) 为中心逆时针旋转 θθ
保证 θ∈(−π,π)θ∈(−π,π)，以弧度制给出。
3 l r a b λ3 l r a b λ：将编号在 [l,r][l,r] 中的点以 (a,b)(a,b) 为中心放缩 ∣λ∣∣λ∣ 倍
即在指向 (a,b)(a,b) 的方向所在直线上移动，距离缩小 (∣λ∣<1∣λ∣<1) 或变大 (∣λ∣>1∣λ∣>1)。
例如 λ=0λ=0 即变为 (a,b)(a,b)，λ<0λ<0 则其相对于 (a,b)(a,b) 的方向会相反。
4 l r θ y04 l r θ y0：将编号在 [l,r][l,r] 中的点以 y=(tan⁡θ)x+y0y=(tanθ)x+y0 为对称轴做对称变换
保证 θ∈(−π2,π2)θ∈(−2π,2π)，以弧度制给出。
例如，θ=0,y0=0θ=0,y0=0 即沿 xx 轴对称。
5 l r θ y05 l r θ y0：将编号在 [l,r][l,r] 中的点投影到 y=(tan⁡θ)x+y0y=(tanθ)x+y0
保证 θ∈(−π2,π2)θ∈(−2π,2π)，以弧度制给出。
例如，θ=0,y0=0θ=0,y0=0 即投影到 xx 轴上。
6 l r 6 l r ：求编号在 [l,r][l,r] 中的点的重心
点集 {(ai,bi)}i=1m{(ai,bi)}i=1m 的重心定义为 (∑i=1mai/m,∑i=1mbi/m)(∑i=1mai/m,∑i=1mbi/m)。
7 l r a b7 l r a b：求编号在 [l,r][l,r] 中的点到 (a,b)(a,b) 的距离的平方的和（注意，不是距离的和的平方）
点集 {(ai,bi)}i=1m{(ai,bi)}i=1m 到 (a,b)(a,b) 的距离的平方的和即 ∑i=1m(ai−a)2+(bi−b)2∑i=1m(ai−a)2+(bi−b)2。
输入格式
从标准输入读入数据。

第一行一个整数 n,qn,q 表示点数和操作数。

接下来 nn 行，每行两个实数表示 (xi,yi)(xi,yi)。

接下来 qq 行，每行若干实数表示一次操作，保证格式同题面。

输出格式
输出到标准输出。

若干行，每行依次对 66 和 77 操作输出两个或一个实数，表示所求的重心坐标或距离平方和。

样例1输入
10 20
26.389153 -31.339463
-98.664509 -58.061567
16.023894 14.489272
-67.840842 -74.793309
19.790708 -87.062719
31.541964 88.441505
-75.918013 24.526470
57.288832 -39.033977
38.274184 -67.446883
-90.906424 -73.528612
3 4 4 32.938694 -6.774595 1.000221
1 2 6 69.965610 -39.563795
4 3 10 -1.399075 38.282976
4 6 7 -1.016301 61.080461
7 9 10 76.549276 22.856189
7 3 7 -96.501727 5.585970
6 8 9
4 2 8 1.215917 -90.918350
7 4 8 55.948842 38.373278
1 5 9 -83.845362 -6.619437
5 6 9 -1.202044 -90.146760
7 1 4 -81.574047 -56.555229
3 1 5 75.690820 60.620104 0.980271
4 5 9 1.512746 89.531420
5 2 5 0.071305 79.784122
6 2 4
1 3 6 90.288492 72.829660
6 4 4
7 1 10 -51.991614 -6.732535
5 5 6 0.087950 71.164056

样例1输出
21029.678359
120220.146461
-14.172376 -63.985055
95006.134951
52111.910474
2.849235 79.987632
35.040886 148.667661

T5 PS无限版
经典的线段树维护区间和，支持区间乘以一个数，只不过这里的数都是矩阵。用一个六维列向量 (x2,y2,xy,x,y,1)T(x^2,y2,xy,x,y,1)^T(x2,y2,xy,x,y,1)T 表示坐标 (x,y)(x,y)(x,y)，不难发现题中提到的所有操作都是对这个向量进行线性变换。由于线性变换具有结合律，因此可以用区间数据结构维护。
cpp 代码解读复制代码

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>/* 描述矩阵运算 */
const int maxM = 6 + 1;
struct Matrix {int n, m; // n 行 m 列矩阵 double A[maxM][maxM];
};/* 计算矩阵乘法 */
Matrix MatMul(const Matrix& A, const Matrix& B) {assert(A.m == B.n);Matrix Ans = {A.n, B.m};    for(int i = 1; i <= A.n; i ++) {for(int j = 1; j <= B.m; j ++) {double tmp = 0;for(int k = 1; k <= A.m; k ++) {tmp += A.A[i][k] * B.A[k][j]; }Ans.A[i][j] = tmp; }}return Ans;
}/* 为矩阵乘法重载运算符 */
Matrix operator*(Matrix A, Matrix B) {return MatMul(A, B);
}/* 计算矩阵加法 */
Matrix MatAdd(Matrix A, Matrix B) {assert(A.n == B.n && A.m == B.m);Matrix Ans = {A.n, B.m};for(int i = 1; i <= A.n; i ++) {for(int j = 1; j <= B.n; j ++) {Ans.A[i][j] = A.A[i][j] + B.A[i][j];}}return Ans;
}/* 为矩阵加法运算重载运算符 */
Matrix operator+(Matrix A, Matrix B) {return MatAdd(A, B);
}/* 用于生成各种计算矩阵 */
namespace MatrixGen {Matrix Node(double x, double y) { // 生成一个结点向量 Matrix tmp = {6, 1, // 列向量 {{}, // line 0{0, x*x}, // line 1{0, y*y}, // line 2{0, x*y}, // line 3{0,   x}, // line 4{0,   y}, // line 5{0,   1}  // line 6}};return tmp;}Matrix Eye() { // 单位矩阵 static const Matrix EYE = {6, 6, // 单位矩阵 {{}, // line 0{0,   1, 0, 0, 0, 0, 0}, // line 1{0,   0, 1, 0, 0, 0, 0}, // line 2{0,   0, 0, 1, 0, 0, 0}, // line 3{0,   0, 0, 0, 1, 0, 0}, // line 4{0,   0, 0, 0, 0, 1, 0}, // line 5{0,   0, 0, 0, 0, 0, 1}  // line 6}};return EYE;}Matrix Zero() { // 单位矩阵 static const Matrix ZERO = {6, 1,{{}, // line 0{0,   0}, // line 1{0,   0}, // line 2{0,   0}, // line 3{0,   0}, // line 4{0,   0}, // line 5{0,   0}  // line 6}};return ZERO;}Matrix Move(double a, double b) { // 平移 x+=a, y+=b Matrix tmp = {6, 6, {{}, // line 0{0,   1, 0, 0, 2*a,   0, a*a}, // line 1: x^2{0,   0, 1, 0,   0, 2*b, b*b}, // line 2: y^2{0,   0, 0, 1,   b,   a, a*b}, // line 3:  xy{0,   0, 0, 0,   1,   0,   a}, // line 4:   x{0,   0, 0, 0,   0,   1,   b}, // line 5:   y{0,   0, 0, 0,   0,   0,   1}  // line 6:   1}};return tmp;}Matrix _Rotate(double theta) { // 绕原点逆时针旋转 theta 弧度 double s = sin(theta), s2 = s*s;double c = cos(theta), c2 = c*c, sc2 = 2*s*c, sc=s*c;Matrix tmp = {6, 6, {{}, // line 0{0,   c2,  s2,  -sc2, 0,  0, 0}, // line 1: x^2{0,   s2,  c2,  +sc2, 0,  0, 0}, // line 2: y^2{0,   sc, -sc, c2-s2, 0,  0, 0}, // line 3:  xy{0,    0,   0,     0, c, -s, 0}, // line 4:   x{0,    0,   0,     0, s,  c, 0}, // line 5:   y{0,    0,   0,     0, 0,  0, 1}  // line 6:   1}};return tmp;}Matrix _Flip() { // 沿着 x 轴对称 : y -> -yMatrix tmp = {6, 6,{{}, // line 0{0,   1, 0, 0, 0, 0, 0}, // line 1: x^2{0,   0, 1, 0, 0, 0, 0}, // line 2: y^2{0,   0, 0,-1, 0, 0, 0}, // line 3:  xy{0,   0, 0, 0, 1, 0, 0}, // line 4:   x{0,   0, 0, 0, 0,-1, 0}, // line 5:   y{0,   0, 0, 0, 0, 0, 1}  // line 6:   1}};return tmp;}Matrix _Project() { // 投影到 x 轴上: y -> 0 Matrix tmp = {6, 6,{{}, // line 0{0,   1, 0, 0, 0, 0, 0}, // line 1: x^2{0,   0, 0, 0, 0, 0, 0}, // line 2: y^2{0,   0, 0, 0, 0, 0, 0}, // line 3:  xy{0,   0, 0, 0, 1, 0, 0}, // line 4:   x{0,   0, 0, 0, 0, 0, 0}, // line 5:   y{0,   0, 0, 0, 0, 0, 1}  // line 6:   1}};return tmp;}Matrix _Resize(double lambda) { // 以原点为中心缩放 double l = fabs(lambda), l2 = l*l;Matrix tmp = {6, 6,{{}, // line 0{0,   l2,  0,  0, 0, 0, 0}, // line 1: x^2{0,    0, l2,  0, 0, 0, 0}, // line 2: y^2{0,    0,  0, l2, 0, 0, 0}, // line 3:  xy{0,    0,  0,  0, l, 0, 0}, // line 4:   x{0,    0,  0,  0, 0, l, 0}, // line 5:   y{0,    0,  0,  0, 0, 0, 1}  // line 6:   1}};return tmp;}/* 以 a, b为中心旋转 */Matrix Rotate(double a, double b, double theta) {Matrix m1 = Move(-a, -b);Matrix m2 = _Rotate(theta);Matrix m3 = Move(a, b);return (m3 * m2) * m1;}/* 以  a, b 为中心缩放 */Matrix Resize(double a, double b, double lambda) {Matrix m1 = Move(-a, -b);Matrix m2 = _Resize(lambda);Matrix m3 = Move(a, b);return (m3 * m2) * m1;}/* 关于直线 y = tan(theta)x + y0 对称 */Matrix Flip(double theta, double y0) {Matrix m1 = Move(0, -y0);Matrix m2 = _Rotate(-theta);Matrix m3 = _Flip();Matrix m4 = _Rotate(+theta);Matrix m5 = Move(0, +y0);return m5 * m4 * m3 * m2 * m1;}/* 投影到直线 y = tan(theta)x + y0*/Matrix Project(double theta, double y0) {Matrix m1 = Move(0, -y0);Matrix m2 = _Rotate(-theta);Matrix m3 = _Project();Matrix m4 = _Rotate(+theta);Matrix m5 = Move(0, +y0);return m5 * m4 * m3 * m2 * m1;}
}const int maxn = (5e5 + 10); // 最大点数 
double _X[maxn], _Y[maxn];namespace SegT { // 维护区间和，允许区间乘一个数 const int maxm = maxn * 2; // 最大结点数 int lch[maxm], rch[maxm], lzy[maxm]; // lzy != 0 表示有 lzy 要被下传 Matrix LazyMat[maxm];                // lzay 矩阵 Matrix SumMat [maxm];                // 区间和矩阵 int ncnt = 0;/* 维护修改 */void maintain(int rt) {SumMat[rt] = SumMat[lch[rt]] + SumMat[rch[rt]];}/* 标记下传 */void pushdown(int rt) {if(lzy[rt]) {if(lch[rt]) {int nl = lch[rt];int nr = rch[rt];/* 修改子节点 Sum */SumMat[nl] = LazyMat[rt] * SumMat[nl]; SumMat[nr] = LazyMat[rt] * SumMat[nr]; /* 修改子节点 lazy */LazyMat[nl] = LazyMat[rt] * LazyMat[nl];LazyMat[nr] = LazyMat[rt] * LazyMat[nr];/* 修改子节点 lazy 标记 */ lzy[nl] = 1;lzy[nr] = 1;}LazyMat[rt] = MatrixGen::Eye(); // 单位矩阵 }lzy[rt] = 0; // 清除标记 }void build(int rt, int l, int r) {if(l == r) {SumMat [rt] = MatrixGen::Node(_X[l], _Y[l]);LazyMat[rt] = MatrixGen::Eye(); }else {int nl = ++ ncnt;int nr = ++ ncnt;int mid = (l + r) >> 1;build(nl, l,   mid);build(nr, mid+1, r);lch[rt] = nl;rch[rt] = nr;/* 修改该 LazyMat 和 SumMat */LazyMat[rt] = MatrixGen::Eye(); maintain(rt);}}/* 在结点上打标记 */void tag(int rt, const Matrix& mat) {if(rt) {SumMat [rt] = mat * SumMat [rt];LazyMat[rt] = mat * LazyMat[rt];lzy[rt] = 1;}}/* 区间乘法 */void update(int rt, int l, int r, int ql, int qr, const Matrix& mat) {if(r  < ql || qr < l) return; // 没有交集 if(ql <= l && r  <= qr) {     // 被包含 tag(rt, mat); return;}pushdown(rt); // 标记下传 int mid = (l + r) >> 1;update(lch[rt],     l, mid, ql, qr, mat);update(rch[rt], mid+1,   r, ql, qr, mat);/* 维护区间和 */maintain(rt);}/* 计算区间和 */Matrix query(int rt, int l, int r, int ql, int qr) {if(r  < ql || qr < l  ) return MatrixGen::Zero(); // 没交集 if(ql <= l && r  <= qr) return SumMat[rt];        // 被包含 pushdown(rt);int mid = (l + r) >> 1;Matrix ml = query(lch[rt],     l, mid, ql, qr);Matrix mr = query(rch[rt], mid+1,   r, ql, qr);/* 维护区间和 */maintain(rt);return ml + mr;}
}int main() {//std::ios::sync_with_stdio(false);int N, Q; std::cin >> N >> Q;for(int i = 1; i <= N; i ++) {//std::cin >> _X[i] >> _Y[i]; // 输入所有点的坐标 scanf("%lf%lf", &_X[i], &_Y[i]);}SegT::build(++ SegT::ncnt, 1, N);for(int i = 1; i <= Q; i ++) { // 处理所有询问 //std::cerr << "[DEBUG] " << "i = " << i << std::endl;//int op; std::cin >> op;int op; scanf("%d", &op);switch(op) {case 1: { // 平移运动 //double ql, qr, a, b; std::cin >> ql >> qr >> a >> b;double ql, qr, a, b; scanf("%lf%lf%lf%lf", &ql ,&qr, &a, &b);SegT::update(1, 1, N, ql, qr, MatrixGen::Move(a, b));break;}case 2: { // a, b, theta 旋转 //double ql, qr, a, b, theta; std::cin >> ql >> qr >> a >> b >> theta;double ql, qr, a, b, theta; scanf("%lf%lf%lf%lf%lf", &ql, &qr, &a, &b, &theta);SegT::update(1, 1, N, ql, qr, MatrixGen::Rotate(a, b, theta));break;}case 3: { // a, b, lambda 缩放 //double ql, qr, a, b, lambda; std::cin >> ql >> qr >> a >> b >> lambda;double ql, qr, a, b, lambda; scanf("%lf%lf%lf%lf%lf", &ql, &qr, &a, &b, &lambda);SegT::update(1, 1, N, ql, qr, MatrixGen::Resize(a, b, lambda));break;}case 4: { // theta, y0 直线轴对称 //double ql, qr, theta, y0; std::cin >> ql >> qr >> theta >> y0;double ql, qr, theta, y0; scanf("%lf%lf%lf%lf", &ql, &qr, &theta, &y0);SegT::update(1, 1, N, ql, qr, MatrixGen::Flip(theta, y0));break;}case 5: { // theta, y0 直线投影 //double ql, qr, theta, y0; std::cin >> ql >> qr >> theta >> y0;double ql, qr, theta, y0; scanf("%lf%lf%lf%lf", &ql, &qr, &theta, &y0);SegT::update(1, 1, N, ql, qr, MatrixGen::Project(theta, y0));break;                }case 6: { // 查询区间重心 //double ql, qr; std::cin >> ql >> qr;double ql, qr; scanf("%lf%lf", &ql, &qr);Matrix tmp = SegT::query(1, 1, N, ql, qr);int len = (qr - ql + 1);//std::cout << tmp.A[4][1] / len << " " << tmp.A[5][1] / len << std::endl;printf("%lf %lf\n", tmp.A[4][1] / len, tmp.A[5][1] / len);break;}case 7: { // a, b 查询区间距离平方和 //double ql, qr, a, b; std::cin >> ql >> qr >> a >> b;double ql, qr, a, b; scanf("%lf%lf%lf%lf", &ql, &qr, &a, &b);SegT::update(1, 1, N, ql, qr, MatrixGen::Move(-a, -b));Matrix tmp = SegT::query(1, 1, N, ql, qr);SegT::update(1, 1, N, ql, qr, MatrixGen::Move(+a, +b));//std::cout << tmp.A[1][1] + tmp.A[2][1] << std::endl;printf("%lf\n", tmp.A[1][1] + tmp.A[2][1]);break;}default:assert(false /* 操作不合法 */ );}}return 0;
}