问题一：
有一类边 A
从A中任选三个组成三角形的方案书可以用fft求解
类似例题
hdu 4609

问题二：
有三类边 A B C
从A，B，C 中各选一条组成三角形的方案数可以用fft求解
类似例题
2019上海icpc网络赛 Triple

问题三
有两类边 A B
从A中选两条边，从B中选一条边，组成三角形的方案数如何求解？

题目描述

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

每个建筑物的几何信息用三元组[Li，Ri，Hi]表示，其中Li和 Ri分别是第i座建筑物左右边缘的x 坐标，Hi是其高度。可以保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX 和 Ri - Li > 0。您可以假设所有建筑物都是在绝对平坦且高度为 0 的表面上的完美矩形。


例如，图A中所有建筑物的尺寸记录为：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。

输出是以[ [x1,y1], [x2, y2], [x3, y3], … ] 格式的“关键点”（图B中的红点）的列表，它们唯一地定义了天际线。关键点是水平线段的左端点。请注意，最右侧建筑物的最后一个关键点仅用于标记天际线的终点，并始终为零高度。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。

例如，图B中的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。

说明:

任何输入列表中的建筑物数量保证在[0, 10000]范围内。
输入列表已经按左x 坐标 Li 进行升序排列。
输出列表必须按 x 位排序。
输出天际线中不得有连续的相同高度的水平线。例如[...[2 3], [4 5], [7 5], [11 5], [12 7]...]是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], …]

算法1

(线性扫描算法) $O(nlogn)$

题解：我们记录每个大楼的左端点和右端点以及对应的高度，然后使用一条扫描线从左向右扫描，每次遇到一个大楼的左端点或者右端点，就有可能是关键点。很直观我们可以得到以下的判别方式。

如果当前扫描到的点是左端点：如果当前左端点p是当前位置上最高的点，那么这一个点是一个关键点(p.left,p.height)。

如果当前扫描到的点是右端点：如果当前右端点p比除了这个右端点之外最高的点q还要高，那么我们形成了一个关键点，这个关键点的坐标就是(p.right,q.height)。

接下来我们就需要考虑如何能够高效的实现支持单点更新的区间最大值（楼的高度），线段树是可以的，但是这道题也没有区间查询，那么我们直接使用一个multiset就可以了，这里使用multiset而不是set是因为多个建筑物可以共享同一个高度。如果遇到左端点，我们就把这个楼的高度加入multiset；如果遇到右端点，我们就把这个楼的高度从multiset中移除。

为了进行线性扫描算法，我们需要先将所有楼的左顶点和右顶点进行按照横坐标进行排序。我们需要考虑如下情况：

如果同一个横坐标有两个左顶点，我们记做p1.height > p2.height那么高度较高的那个左顶点才是真正的关键点，根据关键点判别思路，我们应该先遍历高度较高的那个p1。

如果同一个横坐标有两个右顶点，我们记做p1.height > p2.height，根据关键点判别思路如果先将高度较高的那个移除，就会生成一个(p1.right,p2.height)的错误关键点。所以我们应该先移除高度较小的右端点p2。

如果同一个横坐标有一个左端点p1和一个右端点p2，如果我们先遍历右端点再遍历左端点，我们可能会得到一个错误的关键点。
综上所述，我们对顶点进行排序，应该是按照横坐标从小到大，横坐标相同时，如果都是左端点，先那么遍历较高的那个，如果是右端点，先遍历较矮的那个，如果一个左端点一个右端点，先遍历左端点。基于这种思想，我们使用pair<int,int>来存储端点，如果是左端点，存储<p.left,-p.height>，如果是右端点存储<p.right,p.height>。pair的比较是先基于第一关键字再急于第二关键字的，可以完美的支持上述比较。

我们的算法如下：

1. 先将所有建筑物的左右顶点加入到events中，使用一个multiset支持排序。

2. 为了处理边界情况先在height中添加一个0。

3. 从左向右遍历每一个event：

如果是左端点，如果其高度大于当前位置最大高度加入答案，同时将高度加入height的multiset。

如果是右端点，先将该高度移除出height，如果其高度高于新的height的最大值，那么是一个关键点。

C++ 代码

    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> res;
        multiset<pair<int,int>> events;
        multiset<int> height;
        height.insert(0);
        int n = buildings.size();
        for(int i = 0 ; i < n ; i ++)
        {
            events.insert(make_pair(buildings[i][0],-buildings[i][2]));
            events.insert(make_pair(buildings[i][1],buildings[i][2]));            
        }
        for(auto p:events)
        { 
            if(p.second < 0)
            {
                if(-p.second > *height.rbegin())
                    res.push_back({p.first,-p.second});
                height.insert(-p.second);
            }
            else
            {
                height.erase(height.find(p.second));
                if(p.second > *height.rbegin())
                    res.push_back({p.first,*height.rbegin()});
            }
        }
        return res;
    }

题目描述

因为自己在写二分的时候习惯了左闭右开的写法，而且觉得左闭右开会更美观一些，所以打算把全部的模板都用左闭右开的方式写一遍。

C++代码

#include <iostream>

using namespace std;

int nums[100010], temp[100010];
int n;
void merge_sort(int nums[], int l, int r) {
    if (l >= r-1) return;
    int mid = l + (r - l) / 2;
    merge_sort(nums, l, mid); 
    merge_sort(nums, mid, r);
    int k = 0, i = l, j = mid;
    while (i < mid && j < r) {
        if (nums[i] < nums[j]) 
            temp[k++] = nums[i++];
        else temp[k++] = nums[j++];
    }
    while (i < mid) {
        temp[k++] = nums[i++]; 
    }
    while (j < r) {
        temp[k++] = nums[j++];
    }
    for (k = 0, i = l; i < r; i++, k++) {
        nums[i] = temp[k];
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin>>nums[i];
    }
    merge_sort(nums, 0, n);
    for (int i = 0; i < n; i++) {
        cout<<nums[i]<<' ';    
    }
}

rt
lz已用尽所学各路优化
外加重构代码3遍

建立一棵二叉树
输出所有的叶子节点和数量
输出二叉树深度并解释一下公式
斐波那契用树实现并解释
感谢大佬
祝在CSP一切顺利杀进复赛！！！

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAXN = 1e6+10;

int arr[MAXN];
int N,M;

int main(){
    scanf("%d%d",&N,&M);
    for(int i = 0; i < N; i++){
        scanf("%d",&arr[i]);
    }
    for(int i = 0; i < M; i++){
        int a;
        int start = -1,end = -1;
        scanf("%d",&a);
        //求upper_bound
        int l = 0, r = N-1;
        while(l < r){
            int mid = l+r+1>>1;
            if(arr[mid] <= a) l = mid;
            else r = mid-1;
        }
        if(arr[l] == a) start = l;
        //求lower_bound
        l = 0, r = N-1;
        while(l < r){
            int mid = l+r>>1;
            if(arr[mid] >= a) r = mid;
            else l = mid+1;
        }
        if(arr[l] == a) end = l;
        printf("%d %d\n",end,start);
    }
    return 0;
}

跟隔壁的雨天的尾巴 （大佬代码实现原理参照）异常相似
线段树合并入门

1.Analysis

某条路线对当前节点x有贡献时只可能是

x在s到t的路线上（即s到lca到t）

那么首先我们可以对从s到t的路线划分为

从s到lca(s,t)

以及从t到lca

a.

from s to lca
要有贡献

易得dep[s]-dep[x]=valx

观察可得寻找s满足dep[s]=dep[x]+val[x]的数量

b.

from lca to t
要有贡献

易得dep[s]+dep[x]-dep[lca]-dep[lca]=valx

观察可得寻找s满足dep[s]-dep[lca]-dep[lca]=val[x]-dep[x]的数量

为了计算.我们规定lca被算在a部分中

2.实现

a.

不断从叶子到lca累加
易联想到差分

b.

由于种类不同可以开权值线段树
在递归回fa时合并线段树

3.问题

炸空间

4.解决

就权值线段树合并后空余节点进行一波垃圾回收

code

由于当前编译器有毒，我就不放代码了
QAQ

简单难度谁顶得住啊

两遍bfs，按拓扑序找必经边
先建正图，从S出发，cnt1[i]表示从S出发到i的路径数
再建反图，从T出发，类似的求出cnt2

对于边 i = （u,v,w);
如果cnt1[u] * cnt2[v] == cnt1[T] 则说明 i 是必经边

再找出最短路，在最短路上进行dp
找最短路过程可以和bfs一起进行
单向边所以要走正图找最短路
先走反图再走正图
用pre记入边即可
因为要建反图，肯定是要把边都存下来的

dp找从S出发和从T出发只乘一次车最多少走的桥长
ds[i]代表从S出发到i车走过桥的长度
i只用枚举整点，因为如果不在整点一定可以移到整点让答案不会更差
车肯定是跑的越多越好
所以k记录最早从哪上车，直接用k转移即可
dt从T出发，与ds类似
最后枚举ds,dt的分割点，求出两次车最最多覆盖的桥长即可

还有一个证明，就是随机找最短路不影响结果：
首先，因为桥在所有路径上,所以桥一定在最短路上
把两个桥中间的部分单独来看，只关心长度而不关心具体路径
即证

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1e5+5,M = 2*N,inf = 0x3f3f3f3f,mod = 1e9 + 7;

int tot,S,T,n,m,q,idx = 1,ver[M],wet[M],nxt[M],head[N],dis[N],indu[N],edu[M],edv[M],edw[M],pre[N];
queue<int> q1;
bool bridge[M];
LL dt[N],ds[N],cnt1[N],cnt2[N],sum_b[N],sum[N];

void add(int u,int v,int w)
{
    nxt[++idx] = head[u];
    ver[idx] = v;
    wet[idx] = w;
    head[u] = idx;
}

void bfs(int st,LL a[])
{
    memset(dis,inf,sizeof dis);
    a[st] = 1;
    q1.push(st);
    dis[st] = 0;

    while(q1.size())
    {
        int u = q1.front();q1.pop();
        for(int i = head[u]; i ;i = nxt[i])
        {
            int v = ver[i];
            indu[v] --;
            if(!indu[v])q1.push(v);
            a[v] = (a[u] + a[v]) % mod;
            if(dis[v] > dis[u] + wet[i])
                dis[v] = dis[u] + wet[i],pre[v] = i - 1;
        }
    }
}

void init()
{
    memset(head,0,sizeof head);
    memset(bridge,0,sizeof bridge);
    memset(indu,0,sizeof indu);
    memset(pre,0,sizeof pre);
    memset(ds,0,sizeof ds);
    memset(dt,0,sizeof dt);
    memset(sum,0,sizeof sum);
    memset(sum_b,0,sizeof sum_b);
    idx = 1;
    tot = 0;
}

void get_path(int x)
{
    if(x != S)get_path(edu[pre[x]]);
    ++tot;
    sum_b[tot] += sum_b[tot-1] + bridge[pre[x]] * edw[pre[x]];
    sum[tot] += sum[tot-1] + edw[pre[x]];
}

void dp()
{
    int k = 1;
    for(int i = 2;i <= tot;i ++)
    {
        while( sum[i] - sum[k] > q )k++;
        ds[i] = max(ds[i-1],sum_b[i] - sum_b[k] + (sum_b[k] - sum_b[k-1] > 0 ? q - (sum[i] - sum[k]) : 0 ) );
    }

    k = tot;

    for(int i = tot - 1;i >= 1;i --)
    {
        while( sum[k] - sum[i] > q )k--;
        dt[i] = max(dt[i+1],sum_b[k] - sum_b[i] + (sum_b[k+1] - sum_b[k] > 0 ? q - (sum[k] - sum[i]) : 0 ) );
    }
}

int main()
{
    int L;
    cin >> L;
    while(L --)
    {
        init();
        scanf("%d%d%d%d%d",&n,&m,&S,&T,&q);
        S++,T++;
        int xi,yi,zi;
        for(int i = 1;i <= m;i ++)
            scanf("%d%d%d",&xi,&yi,&zi),add(++yi,++xi,zi),indu[xi]++,edu[i] = xi,edv[i] = yi,edw[i] = zi;

        memset(cnt2,0,sizeof cnt2);
        bfs(T,cnt2);

        init();
        for(int i = 1;i <= m;i ++)
            add(edu[i],edv[i],edw[i]),indu[edv[i]]++;

        memset(cnt1,0,sizeof cnt1);
        bfs(S,cnt1);

        for(int i = 1;i <= m;i ++)
            bridge[i] = cnt1[edu[i]] * cnt2[edv[i]] % mod == cnt1[T] % mod;

        get_path(T);
        dp();

        LL ans = 0;
        for(int i = 1;i <= n;i ++)
            ans = max(ds[i]+dt[i],ans);

        cout << sum_b[tot] - ans << endl;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

Latex 基本练习

• 例子

$$
\begin{align}
  y = y(x,t) &= A e^{i\theta} \\\\
  &= A (\cos \theta + i \sin \theta) \\\\
  &= A (\cos(kx - \omega t) + i \sin(kx - \omega t)) \\\\
  &= A\cos(kx - \omega t) + i A\sin(kx - \omega t)  \\\\
  &= A\cos \Big(\frac{2\pi}{\lambda}x - \frac{2\pi v}{\lambda} t \Big) + i A\sin \Big(\frac{2\pi}{\lambda}x - \frac{2\pi v}{\lambda} t \Big)  \\\\
  &= A\cos \frac{2\pi}{\lambda} (x - v t) + i A\sin \frac{2\pi}{\lambda} (x - v t)
  \end{align}
$$

$$
\begin{align}
y = y(x,t) &= A e^{i\theta} \\
&= A (\cos \theta + i \sin \theta) \\
&= A (\cos(kx - \omega t) + i \sin(kx - \omega t)) \\
&= A\cos(kx - \omega t) + i A\sin(kx - \omega t) \\
&= A\cos \Big(\frac{2\pi}{\lambda}x - \frac{2\pi v}{\lambda} t \Big) + i A\sin \Big(\frac{2\pi}{\lambda}x - \frac{2\pi v}{\lambda} t \Big) \\
&= A\cos \frac{2\pi}{\lambda} (x - v t) + i A\sin \frac{2\pi}{\lambda} (x - v t)
\end{align}
$$

• 公式一律使用另取一行，并且上下都空一行

• 行间插入 $x = a + b$ $a + b$

• 区间插入 $$x = a + b$￥
  $$x = a + b$$

• 上下标

可以看到 x 元素的上标通过 ^ 符号后接的内容体现，下表通过 _ 符号后接的内容体现，多于一位是要加 {} 包裹的。 笔者习惯先下标后上标的写法，和我的书写习惯一致：x_{balabala}^{bala}，不管你使用哪一种风格，最好自己注意统一，不要混用.
$$
x_{1}^{2}
$$

$$
x_{22}^{(n)}
$$

• 分式

这里就出现了一个 frac{}{} 函数的东西，同样，为了区分这是函数不是几个字母，通过 \frac 转义，于是 frac 被解析成函数，然后第一个 {} 里面的被解析成分子，第二个 {} 被解析成分母。

$$
\frac{1}{1 + \frac{1}{2}}
$$

• 根式

读到这里你已经了解了函数的概念，那么这历久很简单了，语法就是 sqrt[]{} 。[] 中代表是几次根式，{} 代表根号下的表达式
$$\sqrt{2}<\sqrt[3]{3}$$

$$
\sqrt{1+\sqrt[^p!]{1+a^2}}
$$

• 求和积分

这里很容易看出求和函数表达式 sum_{起点}^{终点}表达式，积分函数表达式 int_下限^上限

$$
\sum_{k = 1}^n\frac{1}{k}
$$

$$
\int_a^bf(x)dx
$$

• 空格

紧贴 a\!b
$$a!b$$
没有空格ab
$$
ab
$$
小空格 a\,b
$$
a\,b
$$
中等空格 a\;b
$$
a\;b
$$
大空格 a\ b
$$
a\ b
$$
quad空格 a\quad b
$$
a\quad b
$$
两个quad空格 a\qquad b
$$
a\qquad b
$$
这个直接看上面的文字，介绍很清楚，主要指微调距离，使得公式更加漂亮。请比较下面的积分公式
$$
\int_a^bf(x)\mathrm{d}x
$$
$$
\int_a^bf(x)\,\mathrm{d}x
$$

• 公式界定符

通过 \left 和 \right 后面跟界定符来对同时进行界定

\left(\sum_{k=\frac{1}{2}}^{N^2}\frac{1}{k}\right)

$$
\left(\sum_{k=\frac{1}{2}}^{N^2}\frac{1}{k}\right)
$$

$$
\left|\sum_{k=\frac{1}{2}}^{N^2}\frac{1}{k}\right|
$$

• 多行

\\\\用来换行，&=用来对齐等号, \begin{align}``\end{align}用来写多行
$$
\begin{align}
x&= a + b \\
y&= a_1 + a_2 + b \\
z&= a_1 + a_2 + b_1 + b_2 \\
\end{align}
$$

• 参考：fitzeng，typora

#include <bits/stdc++.h>
#define N 100010
#define MOD 100007
#define Re register
#define In inline
using namespace std;
//int ar[N];
In int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int main()
{
    vector<int> ar;
    int n,q,k;
    n=read();q=read();
    for(Re int i=0;i<n;i++){
        ar[i]=read();
    }
    while(q--){
        k=read();
        if(1){
            int pos1=find(ar.begin(),ar.end(),k);
            int pos2=find_if(ar.begin(),ar.end(),bind2nd(greater<int>(),k));
            cout<<distance(pos1,pos2)+1<<endl;
            continue;
    }
        else cout<<"-1 -1"<<endl;
    return 0;
}
}