4.5万

arisingstar
zzp
jasonho
Leonis
edgdcgxgbx
Positive_5
zombotany
NBxiang

Jackyc
qwwjh
itdef
Gn_6

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n, m, a[N], b[N];

int main() {
cin >> n >> m;

for (int i = 0; i < n; i ++) cin >> a[i];
for (int j = 0; j < m; j ++) cin >> b[j];

bool flag = false;
for (int i = 0, j = 0; i < n && j < m; i ++, j ++) {
while (j < m && b[j] != a[i]) j ++;
if (i == n - 1) flag = true;
}

if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}


class Solution {
public:
int reverse(int x) {
int res = 0;

while (x) {
if (res > 0 && res > (INT_MAX - x % 10) / 10) return 0;
if (res < 0 && res < (INT_MIN - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};


class Solution {
public:
string convert(string s, int n) {
string res;

if (n == 1) return s;
for (int i = 0; i < n; i ++) {
if (i == 0 || i == n - 1) {
for (int j = i; j < s.size(); j += 2 * n - 2) {
res += s[j];
}
} else {
for (int j = i, k = 2 * n - 2 - i; j < s.size() || k < s.size(); j += 2 * n - 2, k += 2 * n - 2) {
if (j < s.size()) res += s[j];
if (k < s.size()) res += s[k];
}
}
}
return res;
}
};


class Solution {
public:
string longestPalindrome(string s) {
string res;
for (int i = 0; i < s.size(); i ++) {
int l = i - 1, r = i + 1;
while (l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);

l = i, r = i + 1;
while (l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
}
return res;
}
};


class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int tot = nums1.size() + nums2.size();
if (tot % 2 == 0) {
int left = find(nums1, 0, nums2, 0, tot / 2);
int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
return (left + right) / 2.0;
} else {
return find(nums1, 0, nums2, 0, tot / 2 + 1);
}
}

int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
if (nums1.size() - i > nums2.size() - j) {
return find(nums2, j, nums1, i, k);
}

if (k == 1) {
if (nums1.size() == i) return nums2[j];
else return min(nums1[i], nums2[j]);
}

if (nums1.size() == i) return nums2[j + k - 1];
int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
if (nums1[si - 1] > nums2[sj - 1]) {
return find(nums1, i, nums2, sj, k - (sj - j));
} else {
return find(nums1, si, nums2, j, k - (si - i));
}
}
};


class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> heap;

int res = 0;
for (int i = 0, j = 0; i < s.size(); i ++) {
heap[s[i]] ++;
while (heap[s[i]] > 1) heap[s[j ++]] --;
res = max(res, i - j + 1);
}
return res;
}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1), cur = dummy;

int t = 0;
while (l1 || l2 || t) {
if (l1) t += l1->val, l1 = l1->next;
if (l2) t += l2->val, l2 = l2->next;
cur = cur->next = new ListNode(t % 10);
t /= 10;
}

return dummy->next;
}
};


class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// O(n)时间，即是否前面存在一个数。
// si, target - si
unordered_map<int, int> heap;
for (int i = 0; i < nums.size(); i ++) {
int r = target - nums[i];
if (heap.count(r)) return {heap[r], i};
heap[nums[i]] = i;
}

return {};
}
};


2020-03-25 02:10
// 首先模拟，得到解题需要倒着做
// 倒着做，剩下牛中第ai + 1小的数, 再删除数
// 核心操作：1. 从剩余的数中找出第k小的数; 2. 删除某一个数
// 有size的平衡树可以找.
// a1 - an = 1, 树状数组维护前缀和
// x - 1; add(i, -1);
// 找最小的x使得 sum(x) == k, 二分法做
// 为什么？因为这里特殊，每一位为标志位，sum[k]表示前面有k个数，而每个索引递增，所以即第k小的数。
#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], ans[N], tr[N]; // 数学题

int lowbit(int x) {
return x & -x;
}

void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int sum(int x) {
int ans = 0;
for (int i = x; i; i -= lowbit(i)) ans += tr[i];
return ans;
}

int main() {
scanf("%d", &n);

for (int i = 2; i <= n; i ++) cin >> a[i];

for (int i = 1; i <= n; i ++) add(i, 1);

for (int i = n; i; i --) {
int k = a[i] + 1; // 最小的第k小的数
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (sum(mid) >= k) r = mid;
else l = mid + 1;
}
ans[i] = l; // 找到的坐标就是该数
}

for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
return 0;
}



2020-03-24 16:41

# sum_i sum_x bi

b1
b1 b2
b1 b2 b3

b1 … bx

= (b1 + b2 + .. + bx) * (x + 1) - sum(x * bx)

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和

int lowbit(int x)
{
return x & -x;
}

void add(LL tr[], int x, LL c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}

LL prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ )
{
int b = a[i] - a[i - 1];
}

while (m -- )
{
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
else
{
scanf("%d", &d);
// a[l] += d