4744

889
_Airヾ梦及丨

TonyStank
tideline
puyagang
._723
bluehat

257973846
LC.
Teardrop
IceCola丶

2019-11-01 07:24

### 程序说明

alls 用于储存增加和查询的所有数轴上的点， sum 用于保存前缀和结果，
add 保存需要添加的操作，包括数轴位置和值，query 保存询问的左右边界

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int find (const vector<int>& alls, const int& x)
{
int l = 0, r = alls.size()-1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}

int main ()
{
// 读入n和m
int n, m;
scanf ("%d%d", &n, &m);

vector<int> sum(n + 2 * m + 1, 0), alls;

// 读入数据
for (int i = 0; i < n; i++)
{
int x, c;
scanf("%d%d", &x, &c);
alls.push_back(x);
}
for (int i = 0; i < m; i++)
{
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}

//排序并去重
sort (alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

// 预处理，将alls的数据映射到1 — n + 2*m
for (int i = 0; i < add.size(); i++)
{
}

// 求前缀和
for (int i = 1; i < sum.size(); i++)
sum[i] += sum[i-1];

// 查询
for (int i = 0; i < query.size(); i++)
{
int l = find(alls, query[i].first);
int r = find(alls, query[i].second);
printf ("%d\n", sum[r] - sum[l - 1]);
}
return 0;

}


2019-10-31 02:29

### c++代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// res = A / b, r = A % b;
string div(const string& A, const int& b, int& r)
{
string res;

for (int i = 0; i < A.size(); i++)
{
r = r * 10 + (A[i] - '0');
res += (r / b) + '0';
r %= b;
}

while (res.size() > 1 && res.front() == '0') res = res.substr(1);

return res;
}

int main ()
{
ios::sync_with_stdio(false);
string A;
int b;

cin >> A >> b;

int r = 0;

cout << div(A, b, r) << endl;
cout << r << endl;
return 0;
}


2019-10-31 02:12

### 时间复杂度o(n)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// res = A * B
string mul(const string& A, const int b)
{
string res;

for (int i = A.size() - 1, t = 0; i >= 0 || t > 0; i--)
{
if (i >= 0) t += (A[i] - '0') * b;
res += (t % 10) + '0';
t /= 10;
}
reverse(res.begin(), res.end());
return res;
}

int main ()
{
ios::sync_with_stdio(false);
string A;
int b;
cin >> A >> b;
cout << mul(A, b) << endl;
return 0;
}


2019-10-30 09:50

### 使用string处理大数的减法

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string sub(const string& A, const string& B)
{
string C;
int t = 0;

for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || t > 0; i--, j--)
{
if (i >= 0) t = (A[i] - '0') - t;
if (j >= 0) t -= (B[j] - '0');
C += ((t + 10) % 10 + '0');
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == '0') C.pop_back();
reverse(C.begin(), C.end());
return C;
}

bool cmp(const string& A, const string& B)
{
if (A.size() != B.size()) return A.size() > B.size();
for (int i = 0; i < A.size(); i++)
if (A[i] != B[i]) return A[i] > B[i];
return true;
}

int main ()
{
ios::sync_with_stdio(false);

string A, B;
cin >> A >> B;

if (cmp(A, B)) cout << sub(A, B) << endl;
else cout << "-" << sub(B, A) << endl;

return 0;
}


2019-10-30 09:21

### c++代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// C = A + B;
string add(const string& A, const string& B)
{
string C;
int t = 0;
for (int i = A.size()-1, j = B.size()-1; i >= 0 || j >= 0 || t > 0; i--, j--)
{
if (i >= 0) t += (A[i] - '0');
if (j >= 0) t += (B[j] - '0');
C += ((t % 10) + '0');
t /= 10;
}

reverse(C.begin(), C.end());
return C;
}

int main()
{
ios::sync_with_stdio(false);
string A, B;
cin >> A >> B;
cout << add(A, B) << endl;
return 0;
}



2019-10-29 09:11

### 题目描述

1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

#### 样例

5 3
2 1 3 6 4
1 2
1 3
2 4

3
6
10


### 算法1

##### 目前能想到的最省空间和时间的做法
#include <iostream>
#include <vector>

using namespace std;

int main ()
{
int n, q;
scanf("%d %d", &n, &q);
vector<int> sum(n+1, 0);
for (int i = 1; i <= n; i++)
{
scanf("%d", &sum[i]);
sum[i] += sum[i - 1];
}
while (q--)
{
int l, r;
scanf("%d %d", &l, &r);
printf("%d\n", sum[r] - sum[l-1]);
}
return 0;
}