二分查找（两种模板）/高精度 (加 减) 计算模板（2023/8/30）

//二分查找（两种模板）

#include<iostream>
using namespace std;
#define N 100001
int a[N];
int main()
{
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (m--)
{
int x; scanf("%d", &x);
int l = 0; int r = n - 1;
  while (l < r)
  {
    int mid = (l + r) / 2;//按照左边二分查找
    if (x <= a[mid]) r = mid;//先判断左边
    else l = mid + 1;
  }
 if (a[l] != x) cout << "-1 -1" << endl;
 else
 {
 cout << l << " ";
 int l = 0; int r = n - 1;
   while (l < r)
   {
   int mid = (l + r + 1) / 2;//按照右侧二分查找
   if (x >= a[mid]) l = mid;//先判断右边
   else r = mid - 1;//上加下减
   }
  cout << l << endl;
}

}
return 0;
}

//高精度加法模板

#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> Add(vector<int>& a, vector<int>& b)
{
    int t = 0; vector<int>c;//t是余数
    for (int i = 0; i < a.size() || i < b.size(); i++)
    {
          if(i<a.size()) t += a[i];//a和b一定要分开加，因为位数不确定，没走完的继续加
          if(i<b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);//判断最后是否进位，进位加1
    return c;
}
int main() 
{
    string s1, s2; vector<int>A, B;
    cin >> s1 >> s2;
    for (int i = s1.size() - 1; i >= 0; i--) A.push_back(s1[i]-'0');//注意一定不要忘了减0，不然就不是整数类型了
    for (int i = s2.size() - 1; i >= 0; i--) B.push_back(s2[i]-'0');
    auto C = Add(A, B);//auto 自动识别类型
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    cout << endl;

}



//高精度减法模板

#include<iostream>
#include<vector>
#include<string>
using namespace std;

bool cmp(string& s1, string& s2)//比较输入的两个数的大小，确定加不加负号
{
  if (s1.size() != s2.size()) return s1.size() > s2.size();
  for (int i = 0; i < s1.size(); i++)
    if (s1[i] != s2[i]) return s1[i] > s2[i];
  return true;
}

vector<int> sub(vector<int>& a, vector<int>& b)
{
  vector<int>c; int t = 0;//t为余数
  for (int i = 0; i < a.size(); i++)
  {
    t = a[i] - t;//这一位减去上一个借位
    if (i < b.size()) t -= b[i];//注意b存在才减去b，不然不减
       c.push_back((t + 10) % 10);//最关键 
    if (t < 0)  t = 1;//看借位
    else  t = 0;
}

while (c.size() > 1 && c.back() == 0) c.pop_back();//去掉前导0
return c;
}

int main()
{
string s1, s2; vector<int>a, b, c;
cin >> s1 >> s2;
for (int i = s1.size() - 1; i >= 0; i--) a.push_back(s1[i] - '0');//记住一定减去‘0’,不然不是整数
for (int i = s2.size() - 1; i >= 0; i--) b.push_back(s2[i] - '0');
if (cmp(s1, s2)) c = sub(a, b);
else c = sub(b, a), cout << "-";//添加负号
for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
cout << endl;
return 0;
}