




## 基础

### 圆周率

```cpp
const double pi=acos(-1);
```

### 偏差值

```cpp
const double eps=1e-8;
```

一般取 1e-8，再小可能就出问题了

### 符号函数

```cpp
inline int sgn(double x){return fabs(x) =eps?0:(x 0?1:-1);}
```

### 浮点数输出

当输出浮点数的 0 时，可能会出现输出了 `-0.00000...` 的情况，某些题目中需要特判：

```cpp
inline double fit(double x){return sgn(x)==0?0:x;}
```

### 精度问题

1. 能整数解决的问题就不要使用浮点数。同时注意，如果运算过程中都是整数，但还是用double类型，还是会发生精度损失
2. 使用 long double 减少精度损失
3. 把所有数放大 1000 倍减少精度损失

## 点

### 表示

```cpp
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
```

### 两点距离公式

```cpp
inline double dis(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
```

### 判等

```cpp
bool operator==(Point b){return sgn(x-b.x)==0  sgn(y-b.y)==0;}
```

## 向量

### 表示

可以直接用点来表示向量。把所有向量视为起点为原点

```cpp
typedef Point Vector;
```

### 向量运算

```cpp
Point operator+(Point b){return Point(x+b.x,y+b.y);}
Point operator-(Point b){return Point(x-b.x,y-b.y);}
Point operator*(double k){return Point(x*k,y*k);}
Point operator/(double b){return Point(x/k,y/k);}
```

### 点积

```cpp
double operator*(Point b){return x*b.x+y*b.y;}
```

#### 求向量模长

```cpp
inline double len(Point a){return sqrt(a*a);}
```

有时开方会损失精度，可以改为求长度的平方

```cpp
inline double len2(Point a){return a*a;}
```

#### 夹角

返回的是 cos 值

```cpp
inline double angle(Point a,Point b){return a*b/len(a)/len(b);}
```

### 叉积

```cpp
double operator^(Point b){return x*b.y-y*b.x;}
```

#### 面积

以 a 为 公共点，b 到 c 的有向面积

```cpp
inline double area(Point a,Point b,Point c){return (b-a)^(c-a);}
```

#### 向量旋转与法向量

向量 $(x,y)$ 绕原点逆时针旋转度数 $\theta$，得到向量 $(x',y')$，有如下关系：
$$
x'=x \cos \theta - y \sin \theta \\
y'=x \sin \theta + y \cos \theta
$$

```cpp
inline Point rotate(Point a,double rad){return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
```

法向量为向量逆时针旋转 $90^{\circ} $

```cpp
inline Point normal(Point a){return Point(-a.y/len(a),a.x/len(a));}
```

## 线

### 表示

```cpp
struct Line{
    Point s,t;
    Line(){}
    Line(Point s,Point t):s(s),t(t){}
};
```

### 斜率

```cpp
inline double slope(Point a,Point b){return (a.y-b.y)/(a.x-b.x);}
```

### 倾斜角

```cpp
inline double angle(Line l){
    double k=atan2(l.s.y-l.t.y,l.s.x-l.t.x);
    if(sgn(k) 0) k+=pi;
    if(sgn(k-pi)==0) k=pi;
    return k;
}
```

### 点与线

#### 点与直线位置

点在直线左边还是右边需要看你是从直线哪个方向观察的，这里传递的线段应视为有向线段，从 s 指向 t

```cpp
inline int plr(Point p,Line l){//0:on -1:left 1:right
    int k=sgn((l.t-l.s)^(p-l.s));
    if(k 0) return -1;
    if(k 0) return 1;
    return 0;
}
```

#### 点是否在线段上

先用叉积判断是否共线，再用点积判断是否在线段上

```cpp
inline bool on_seg(Point p,Line l){return plr(p,l)==0  sgn((p-l.s)*(p-l.t)) =0;}
```

#### 点到直线距离

先叉积求出构成的平行四边形面积，然后面积除以底就得到了高，即点到直线距离

```cpp
inline double dis(Point p,Line l){return fabs((p-l.s)^(l.s-l.t)/dis(l.s,l.t));}
```

#### 点在直线上投影

```cpp
inline Point proj(Point p,Line l){return l.s+(l.t-l.s)*(l.t-l.s)*(p-l.s)/len2(l.t-l.s);}
```

#### 点关于直线对称

```cpp
inline Point symmetry(Point p,Line l){return 2*proj(p,l)-p;}
```

#### 点到线段距离

过点向线段所在直线作垂线，如果垂足落在线段上，那么点到线段的距离为点到直线距离，反之，则为点到线段两端点的最小值

```cpp
inline double dis_seg(Point p,Line l){
    if(sgn((p-l.s)*(l.t-l.s)) 0||sgn((p-l.t)*(l.s-l.t)) 0) return min(dis(p,l.s),dis(p,l.t));
    return dis(p,l);
}
```

### 线与线

#### 两直线位置关系

平行、重合、相交

```cpp
inline int llr(Line l1,Line l2){//0:平行 1:相交 2:重合
    if(sgn((l1.s-l1.t)^(l2.s-l2.t))==0){
        if(plr(l1.s,l2)==0) return 2;
        else return 0;
    }
    return 1;
}
```

#### 两线段位置关系

返回值如下：

0. 不相交
1. 非规范相交：交点在端点上
2. 规范相交：交点在线段内部

```cpp
inline int ssr(Line l1,Line l2){//0:不相交 1:非规范相交 2:规范相交
    int c1=plr(l1.s,l2),c2=plr(l1.t,l2);
    int d1=plr(l2.s,l1),d2=plr(l2.t,l1);
    if(c1*c2 0  d1*d2 0) return 2;
    return (c1==0  on_seg(l1.s,l2))||(c2==0  on_seg(l1.t,l2))||(d1==0  on_seg(l2.s,l1))||(d2==0  on_seg(l2.t,l1));
}
```

#### 线段和直线关系

返回值：

0. 不相交

1. 非规范相交
2. 规范相交
3. 重合

```cpp
inline int slr(Line s,Line l){//0:不相交 1:非规范相交 2:规范相交 3:重合
    int d1=plr(s.s,l),d2=plr(s.t,l);
    if(d1==0  d2==0) return 3;
    if(d1*d2==0) return 1;
    if(d1*d2 0) return 2;
    return 0;
}
```

#### 两直线交点

调用该函数前应确保两条直线存在交点

```cpp
inline Point cp(Line l1,Line l2){
    double s1=(l1.t-l1.s)^(l2.s-l1.s);
    double s2=(l1.t-l1.s)^(l2.t-l1.s);
    return (l2.s*s2-l2.t*s1)/(s2-s1);
}
```

#### 线段与线段距离

设 $P_0$ 和 $P_1$ 构成线段 $L_1$，$P_2$ 和 $P_3$ 构成线段 $L_2$，则 $L_1$ 和 $L_2$ 的距离为：

* 如果 $L_1$ 和 $L_2$ 相交，则为 0
* 反之，则为 $P_0$ 到 $L_2$ ，$P_1$ 到 $L_2$，$P_2$ 到 $L_1$，$P_3$ 到 $L_1$ ，四者距离的最小值

## 基础点线模板汇总

```cpp
const double pi=acos(-1);
const double eps=1e-8;
inline int sgn(double x){return fabs(x) =eps?0:(x 0?1:-1);}
inline double fit(double x){return sgn(x)==0?0:x;}
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator+(const Point  b) const {return Point(x + b.x, y + b.y);}
    Point operator-(const Point  b) const {return Point(x - b.x, y - b.y);}
    Point operator*(double k) const {return Point(x * k, y * k);}
    double operator*(const Point  b) const {return x * b.x + y * b.y;}
    Point operator/(double k) const {return Point(x / k, y / k);}
    double operator^(const Point  b) const {return x * b.y - y * b.x;}
};
typedef Point Vector;
struct Line{
    Point s,t;
    Line(){}
    Line(Point s,Point t):s(s),t(t){}
};
inline double dis(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
inline double dis(Point p,Line l){return fabs((p-l.s)^(l.s-l.t)/dis(l.s,l.t));}
inline double len(Point a){return sqrt(a*a);}
inline double len2(Point a){return a*a;}
inline double slope(Point a,Point b){return (a.y-b.y)/(a.x-b.x);}
inline double angle(Point a,Point b){return a*b/len(a)/len(b);}
inline double angle(Line l){
    double k=atan2(l.s.y-l.t.y,l.s.x-l.t.x);
    if(sgn(k) 0) k+=pi;
    if(sgn(k-pi)==0) k=pi;
    return k;
}
inline double area(Point a,Point b,Point c){return (b-a)^(c-a);}//a为公共点，b到c有向面积
inline Point rotate(Point a,double rad){return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
inline Point normal(Point a){return Point(-a.y/len(a),a.x/len(a));}//逆时针旋转90度的法向量
inline int plr(Point p,Line l){//0:on -1:left 1:right
    int k=sgn((l.t-l.s)^(p-l.s));
    if(k 0) return -1;
    if(k 0) return 1;
    return 0;
}
inline bool on_seg(Point p,Line l){return plr(p,l)==0  sgn((p-l.s)*(p-l.t)) =0;}
inline Point proj(Point p,Line l){return l.s+(l.t-l.s)*((l.t-l.s)*(p-l.s))/len2(l.t-l.s);}
inline Point symmetry(Point p,Line l){return proj(p,l)*2-p;}
inline double dis_seg(Point p,Line l){
    if(sgn((p-l.s)*(l.t-l.s)) 0||sgn((p-l.t)*(l.s-l.t)) 0) return min(dis(p,l.s),dis(p,l.t));
    return dis(p,l);
}
inline int llr(Line l1,Line l2){//0:平行 1:相交 2:重合
    if(sgn((l1.s-l1.t)^(l2.s-l2.t))==0){
        if(plr(l1.s,l2)==0) return 2;
        else return 0;
    }
    return 1;
}
inline int ssr(Line l1,Line l2){//0:不相交 1:非规范相交 2:规范相交
    int c1=plr(l1.s,l2),c2=plr(l1.t,l2);
    int d1=plr(l2.s,l1),d2=plr(l2.t,l1);
    if(c1*c2 0  d1*d2 0) return 2;
    return (c1==0  on_seg(l1.s,l2))||(c2==0  on_seg(l1.t,l2))||(d1==0  on_seg(l2.s,l1))||(d2==0  on_seg(l2.t,l1));
}
inline int slr(Line s,Line l){//0:不相交 1:非规范相交 2:规范相交 3:重合
    int d1=plr(s.s,l),d2=plr(s.t,l);
    if(d1==0  d2==0) return 3;
    if(d1*d2==0) return 1;
    if(d1*d2 0) return 2;
    return 0;
}
inline Point cp(Line l1,Line l2){
    double s1=(l1.t-l1.s)^(l2.s-l1.s);
    double s2=(l1.t-l1.s)^(l2.t-l1.s);
    return (l2.s*s2-l2.t*s1)/(s2-s1);
}
```

## 多边形

### 表示

一般用下标从 0 开始的 Point 数组表示

### 多边形面积

```cpp
inline double area(Point *pg,int n){
    double res=0;
    for(int i=0;i n;i++) res+=area(Point(0,0),pg[i],pg[(i+1)%n])/2;
    return res;
}
```

### 多边形重心

将多边形三角剖分，计算出每个三角形的重心，然后再以三角形有向面积为权重加权平均

```cpp
inline Point polygon_center(Point *pg,int n){
    Point ans(0,0);
    if(area(pg,n)==0) return ans;
    for(int i=0;i n;i++) ans=ans+(pg[i]+pg[(i+1)%n])*area(Point(0,0),pg[i],pg[(i+1)%n]);
    return ans/area(pg,n)/6;
}
```

### 极角序

三四象限的点极角序最小，排序后是从三四象限的点（如果有）逆时针排序

代码是以原点为基点求的极角序，如果要以其他的点为基点，则需要把所有的点都减去那个基点

```cpp
inline bool pcmp(Point a,Point b){
    auto f=[](Point p){return p.y 0||(p.y==0  p.x 0);};
    if(f(a)!=f(b)) return f(a) f(b);
    else if((a^b)==0) return a.x b.x;
    else return (a^b) 0;
}
```

### 凸包

```cpp
inline int convex_hull(Point *pg,int n,Point *ch){//会将pg排序并去重，返回凸包顶点数，求的的凸包的点均为顶点，不存在两条边共线
    sort(pg,pg+n,[](Point a,Point b){
        if(sgn(a.x-b.x)==0) return sgn(a.y-b.y) 0;
        return sgn(a.x-b.x) 0;
    });
    n=unique(pg,pg+n)-pg;
    int cnt=0;
    for(int i=0;i n;i++){
        while(cnt =2  sgn((ch[cnt-1]-ch[cnt-2])^(pg[i]-ch[cnt-1])) =0) cnt--;
        ch[cnt++]=pg[i];
    }
    int t=cnt;
    for(int i=n-2;i =0;i--){
        while(cnt =t+1  sgn((ch[cnt-1]-ch[cnt-2])^(pg[i]-ch[cnt-1])) =0) cnt--;
        ch[cnt++]=pg[i];
    }
    if(n =2) cnt--;
    return cnt;
}
```

### 点在多边形内

#### 射线法

适用于任意多边形。具体原理是从要判断的点水平作射线，穿过了奇数条边则说明在多边形内部，反之则在多边形外部

但有几个特殊情况：如果遇到一个水平的边，则应视为没有穿过边；穿过了两条边交界处，应视为穿过了一个边；穿过了两条边构成的一个角的顶点，则应视为没有穿过边。其中前一种可以特判，后一种可以采取把线段看成上闭下开的形式来解决

```cpp
inline bool in_polygon(Point p,Point *pg,int n){// pg下标从0开始，在边上也算
    int ans=0;
    Point p1,p2;
    p1=pg[0];
    for(int i=1;i =n;i++){
        p2=pg[i%n];
        if(on_seg(p,Line(p1,p2))) return true;
        if(p1.y==p2.y){// 水平边不考虑
            p1=p2;
            continue;
        }
        if(p.y min(p1.y,p2.y)    p.y =max(p1.y,p2.y)    p.x =max(p1.x,p2.x)){//上取下不取
            if(p1.x==p2.x) ans++;
            else{
                double x=p1.x+(p.y-p1.y)/slope(p1,p2);
                if(p.x =x) ans++;
            }
        }
        p1=p2;
    }
    return ans 1;
}
```

时间复杂度 $O(n)$

#### 叉乘判断

只适用于判断点是否在凸包内

逐个计算点到凸包顶点构成的向量之间的叉乘是否是同号，即判断这些向量是否都往一个方向转，是的话就说明点在该凸包内

![](https://pic.caiwen.work/i/2025/02/18/67b46f833d5ba.png)

时间复杂度 $O(n)$

#### 二分法

只适用于凸包

首先把多边形划分为多个区域

![](https://pic.caiwen.work/i/2025/02/18/67b4701ee315a.png)

![](https://pic.caiwen.work/i/2025/02/18/67b470cc6b966.png)

如果要判断一个点是否在该凸包内，则先找到这个点在哪个区域内。如果不在这几个区域中，则必不在凸包内，否则我们只需要判断这个点和凸包的边的关系即可

![](https://pic.caiwen.work/i/2025/02/18/67b470e7ee9a7.png)

时间复杂度 $O(\log n)$

```cpp
int n,m,k,ok=0,cnt=1;cin  n  m  k;
for(int i=0;i n;i++) cin  p[i].x  p[i].y;
n=convex_hull(p,n,ch);
Point base=p[0];
for(int i=0;i n;i++) ch[i]=ch[i]-base;
while(m--){
    Point now;cin  now.x  now.y;
    now=now-base;
    if(plr(now,Line(ch[0],ch[1]))==0||plr(now,Line(ch[0],ch[n-1]))==0){
        if(on_seg(now,Line(ch[0],ch[1]))||on_seg(now,Line(ch[0],ch[n-1]))) ok++;
        continue;
    }
    if(!(plr(now,Line(ch[0],ch[1]))==-1  plr(now,Line(ch[0],ch[n-1]))==1)) continue;
    int l=1,r=n-1,ans=-1;
    while(l =r){
        int mid=(l+r)  1;
        if((ch[mid]^now) =0) ans=mid,l=mid+1;
        else r=mid-1;
    }
    if(ans==-1||ans==n-1) continue;
    if(plr(now,Line(ch[ans],ch[ans+1]))!=1) ok++;
}
if(ok =k) cout  "YES"  endl;
else cout  "NO"  endl;
```

## 其他

### 平面最近点对

```cpp
Point p[_];
int tmp[_];
double solve(int l,int r){
    if(l==r) return inf;
    if(l+1==r) return dis(p[l],p[r]);
    int mid=(l+r)  1,cnt=0;
    double d1=solve(l,mid),d2=solve(mid+1,r),d=min(d1,d2);
    for(int i=l;i =r;i++) if(fabs(p[mid].x-p[i].x) d) tmp[++cnt]=i;
    for(int i=1;i =cnt;i++){
        for(int j=1;j i;j++){
            double d3=dis(p[tmp[i]],p[tmp[j]]);
            d=min(d,d3);
        }
    }
    return d;
}
inline void subtask(){
    int n;cin  n;
    for(int i=1;i =n;i++) cin  p[i].x  p[i].y;
    sort(p+1,p+n+1,[](Point a,Point b){return sgn(a.x-b.x)==0? sgn(a.y-b.y) 0:sgn(a.x-b.x) 0;});
    double res=solve(1,n);
    printf("%.4lf",res);
}
```









## 整体二分

整体二分的基本思想是，二分出一个 $mid$，然后遍历所有的询问，每个询问都 check 一下 mid 是偏大了还是偏小了。把偏大的询问分成一组，偏小的询问分成另一组。然后这两组询问再分别二分

### P3332 [ZJOI2013] K大数查询

https://www.luogu.com.cn/problem/P3332

**题目描述**

你需要维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。  

这些集合初始都是空集，有 $m$ 个操作：  

- `1 l r c`：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中  
- `2 l r c`：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。  

注意可重集的并是不去除重复元素的，如 $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$。

**数据范围**

$1 \le n,m \le 5\times 10^4$ 

$1\le l,r \le n$ 

$1$ 操作中 $|c|\le n$ 

$2$ 操作中 $1\le c   2^{63}$，第 $c$ 大的数存在

**笔记**

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 50004
int n,arr[_],m,sum[_  2],tag[_  2];
inline void pushup(int k){sum[k]=sum[ls(k)]+sum[rs(k)];}
inline void pushadd(int k,int l,int r,int v){sum[k]+=v*(r-l+1),tag[k]+=v;}
inline void pushdown(int k,int l,int r,int mid){if(tag[k])pushadd(ls(k),l,mid,tag[k]),pushadd(rs(k),mid+1,r,tag[k]),tag[k]=0;}
void modify(int k,int l,int r,int x,int y,int v){
    if(l =x  r =y) return pushadd(k,l,r,v),void();
    int mid=(l+r)  1;
    pushdown(k,l,r,mid);
    if(x =mid) modify(ls(k),l,mid,x,y,v);
    if(y mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l =x  r =y) return sum[k];
    int mid=(l+r)  1,res=0;
    pushdown(k,l,r,mid);
    if(x =mid) res+=query(ls(k),l,mid,x,y);
    if(y mid) res+=query(rs(k),mid+1,r,x,y);
    return res;
}
struct Q{int l,r,x,id,ans,op;} L[_],R[_],q[_];
void solve(int l,int r,int ql,int qr){
    if(ql qr) return;
    if(l==r){
        for(int i=ql;i =qr;i++) if(q[i].op==2) q[i].ans=l;
        return;
    }
    int mid=(l+r)  1;
    int cntl=0,cntr=0;
    for(int i=ql;i =qr;i++){
        if(q[i].op==1){
            if(q[i].x mid) modify(1,1,n,q[i].l,q[i].r,1),R[++cntr]=q[i];
            else L[++cntl]=q[i];
        }else{
            int cnt=query(1,1,n,q[i].l,q[i].r);
            if(q[i].x =cnt) R[++cntr]=q[i];
            else q[i].x-=cnt,L[++cntl]=q[i];
        }
    }
    for(int i=ql;i =qr;i++) if(q[i].op==1  q[i].x mid) modify(1,1,n,q[i].l,q[i].r,-1);
    for(int i=1;i =cntl;i++) q[ql-1+i]=L[i];
    for(int i=1;i =cntr;i++) q[ql+cntl-1+i]=R[i];
    solve(l,mid,ql,ql+cntl-1);
    solve(mid+1,r,ql+cntl,qr);
}
inline void subtask(){
    cin  n  m;
    for(int i=1;i =m;i++) cin  q[i].op  q[i].l  q[i].r  q[i].x,q[i].id=i;
    solve(-n,n,1,m);
    sort(q+1,q+m+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =m;i++) if(q[i].op==2) cout  q[i].ans  endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

因为我们判断 mid 是偏大了还是偏小了，需要知道比 mid 大的数有多少，因此我们把大于 $mid$ 的 $x$ 值加入线段树。并且，如果询问需要归到 $R$ 中，那么也只有 $x$ 值大于 $mid$ 的操作一会影响到这些询问，因此 $x$ 值大于 $mid$ 的操作也归到 $R$ 中

### P3527 [POI 2011] MET-Meteors

https://www.luogu.com.cn/problem/P3527

**题目描述**

有 $n$ 个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为 $m$ 份（第 $m$ 份和第 $1$ 份相邻），第 $i$ 份上有第 $a_i$ 个国家的太空站。

这个星球经常会下陨石雨。BIU 已经预测了接下来 $k$ 场陨石雨的情况。

BIU 的第 $i$ 个成员国希望能够收集 $p_i$ 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

**输入格式**

第一行是两个数 $n,m$。

第二行有 $m$ 个数，第 $i$ 个数 $o_i$ 表示第 $i$ 段轨道上有第 $o_i$ 个国家的太空站。

第三行有 $n$ 个数，第 $i$ 个数 $p_i$ 表示第 $i$ 个国家希望收集的陨石数量。

第四行有一个数 $k$，表示 BIU 预测了接下来的 $k$ 场陨石雨。 接下来 $k$ 行，每行有三个数 $l_i,r_i,a_i$ ，表示第 $k$ 场陨石雨的发生地点在从 $l_i$ 顺时针到 $r_i$ 的区间中（如果 $l_i \leq r_i$，则是 $l_i, l_i + 1 
\cdots, r_i$，否则就是 $l_i, l_i + 1, 
\cdots m - 1, m, 1, 2, \cdots r_i$），向区间中的每个太空站提供 $a_i$ 单位的陨石样本。

**数据范围**

$1\le n,m,k\le 3\cdot10^5$；

$1\le p_i,a_i\le 10^9$；

**笔记**

把环形的区间加拆成两个操作，然后整体二分即可。整体二分时直接暴力计算每个询问是否满足要求貌似是可以的

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 900005
int arr[_],n,m;
inline int lowbit(int x){return x -x;}
inline void modify(int x,int v){while(x =m) arr[x]+=v,x+=lowbit(x);}
inline int query(int x,int res=0){while(x) res+=arr[x],x-=lowbit(x);return res;}
struct Q{int l,r,id,ans,op,x,need;} q[_],L[_],R[_];
vector int  g[_];
void solve(int l,int r,int ql,int qr){
    if(ql qr) return;
    if(l==r){
        for(int i=ql;i =qr;i++) if(q[i].op==0) q[i].ans=l;
        return;
    }
    int mid=(l+r)  1,cntl=0,cntr=0;
    for(int i=ql;i =qr;i++){
        if(q[i].op==1){
            if(q[i].id =mid) modify(q[i].l,q[i].x),modify(q[i].r+1,-q[i].x),L[++cntl]=q[i];
            else R[++cntr]=q[i];
        }else{
            int s=0;
            for(auto to:g[q[i].x]){
                s+=query(to);
                if(s =q[i].need) break;
            }
            if(s =q[i].need) L[++cntl]=q[i];
            else q[i].need-=s,R[++cntr]=q[i];
        }
    }
    for(int i=ql;i =qr;i++) if(q[i].op==1  q[i].id =mid) modify(q[i].l,-q[i].x),modify(q[i].r+1,q[i].x);
    for(int i=1;i =cntl;i++) q[ql+i-1]=L[i];
    for(int i=1;i =cntr;i++) q[ql+cntl+i-1]=R[i];
    solve(l,mid,ql,ql+cntl-1);
    solve(mid+1,r,ql+cntl,qr);
}
int need[_];
inline void subtask(){
    cin  n  m;
    for(int i=1,x;i =m;i++) cin  x,g[x].push_back(i);
    for(int i=1;i =n;i++) cin  need[i];
    int totq,cntq=0;cin  totq;
    for(int i=1;i =totq;i++){
        int l,r,x;cin  l  r  x;
        if(l =r) q[++cntq].l=l,q[cntq].r=r,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x;
        else q[++cntq].l=1,q[cntq].r=r,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x,q[++cntq].l=l,q[cntq].r=m,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x;
    }
    for(int i=1;i =n;i++) q[++cntq].id=i,q[cntq].x=i,q[cntq].need=need[i];
    //for(int i=1;i =cntq;i++) debug(q[i].op),debug(q[i].l),debug(q[i].r);
    solve(1,totq+1,1,cntq);
    sort(q+1,q+cntq+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =cntq;i++){
        if(q[i].op) continue;
        if(q[i].ans==totq+1) cout  "NIE"  endl;
        else cout  q[i].ans  endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```


