头像

QQ232




离线:11小时前


最近来访(23)
用户头像
yuukilight
用户头像
所见皆是空
用户头像
金州库天日
用户头像
znyee07
用户头像
严小超
用户头像
泷.
用户头像
stitch.
用户头像
希尔维亚
用户头像
Ceil_rogi
用户头像
顶顶.
用户头像
qgxx
用户头像
yxc

活动打卡代码 AcWing 154. 滑动窗口

QQ232
15天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

include[HTML_REMOVED]

using namespace std;

const int N=1e6+10;
int a[N],x[N];

deque[HTML_REMOVED]q;
int minn[N],maxx[N];
int main()
{
int n,k;
scanf(“%d %d”,&n,&k);
for(int i=0;i[HTML_REMOVED]q.front()) q.pop_front();
while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
q.push_back(i);
if(i>=k-1) printf(“%d “,a[q.front()]);
}
cout << endl;
q.clear();
q.push_front(0);
for(int i=1;i[HTML_REMOVED]q.front()) q.pop_front();
while(q.size()&&a[q.back()]<=a[i]) q.pop_back();
q.push_back(i);
if(i>=k-1) printf(“%d “,a[q.front()]);
}
}
return 0;
}



活动打卡代码 AcWing 835. Trie字符串统计

QQ232
18天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

include [HTML_REMOVED]

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;//cnt记录次数,idx是下标 ,son存每个字符的儿子
char str[N];

void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i )
{
int u = str[i] - ‘a’;
if (!son[p][u]) son[p][u] =
idx;
p = son[p][u];
}
cnt[p] ++ ;
}

int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - ‘a’;
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}

int main()
{
int n;
scanf(“%d”, &n);
while (n – )
{
char op[2];
scanf(“%s%s”, op, str);
if (*op == ‘I’) insert(str);
else printf(“%d\n”, query(str));
}

return 0;

}




QQ232
1个月前
#include <bits/stdc++.h>
#define endl '\n'
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>
#define x first
#define y second
#define ALL(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
inline ll in() {
  register ll s = 0, w = 1, 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;
}
void solve();
ll n, m;

template <class T>
class Array_tree {
 public:
  Array_tree() {}
  Array_tree(int n) { this->n = n, tree = vector<T>(n + 1); }
  void add(int id, T key) {
    for (int i = id; i <= n; i += lowbit(i)) tree[i] += key;
  }

  T get_sum(int id) {
    T sum = 0;
    for (int i = id; i; i -= lowbit(i)) sum += tree[i];
    return sum;
  }

  T get_sum(int l, int r) { return get_sum(r) - get_sum(l - 1); }

 private:
  int n;
  vector<T> tree;
  int lowbit(int x) { return x & -x; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  cin >> n >> m;
  Array_tree<ll> tr(n + 1), tri(n + 1);
  vll a(n + 1);
  for (ll i = 1; i <= n; i++) cin >> a[i];
  for (ll i = 1; i <= n; i++) {
    tr.add(i, a[i] - a[i - 1]);
    tri.add(i, i * (a[i] - a[i - 1]));
  }
  while (m--) {
    char op[2];
    cin >> op;
    if (op[0] == 'Q') {
      ll l, r;
      cin >> l >> r;
      ll ans = tr.get_sum(l - 1) * l - tri.get_sum(l - 1);
      ans = tr.get_sum(r) * (r + 1) - tri.get_sum(r) - ans;
      cout << ans << endl;
    } else {
      ll l, r, d;
      cin >> l >> r >> d;
      tr.add(l, d), tr.add(r + 1, -d);
      tri.add(l, l * d), tri.add(r + 1, (r + 1) * (-d));
    }
  }
  return;
}



QQ232
1个月前
#include <bits/stdc++.h>
#define endl '\n'
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>
#define x first
#define y second
#define ALL(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
inline ll in() {
  register ll s = 0, w = 1, 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;
}
void solve();
ll n, m;

template <class T>
class Array_tree {
 public:
  Array_tree() {}
  Array_tree(int n) { this->n = n, tree = vector<T>(n + 1); }
  void add(int id, int key) {
    for (int i = id; i <= n; i += lowbit(i)) tree[i] += key;
  }

  T get_sum(int id) {
    T sum = 0;
    for (int i = id; i; i -= lowbit(i)) sum += tree[i];
    return sum;
  }

  T get_sum(int l, int r) { return get_sum(r) - get_sum(l - 1); }

 private:
  int n;
  vector<T> tree;
  int lowbit(int x) { return x & -x; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  cin >> n >> m;
  Array_tree<ll> tr(n + 1);
  vll a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  while (m--) {
    char op[2];
    cin >> op;
    if (op[0] == 'Q') {
      int x;
      cin >> x;
      cout << a[x] + tr.get_sum(x) << endl;
    } else {
      ll l, r, d;
      cin >> l >> r >> d;
      tr.add(l, d), tr.add(r + 1, -d);
    }
  }
  return;
}


活动打卡代码 AcWing 241. 楼兰图腾

QQ232
1个月前
#include <bits/stdc++.h>
#define endl '\n'
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>
#define x first
#define y second
#define ALL(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
inline ll in() {
  register ll s = 0, w = 1, 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;
}
void solve();
ll n, m;

template <class T>
class Array_tree {
 public:
  Array_tree() {}
  Array_tree(int n) { this->n = n, tree = vector<T>(n + 1); }
  void add(int id, int key) {
    for (int i = id; i <= n; i += lowbit(i)) tree[i] += key;
  }

  T get_sum(int id) {
    T sum = 0;
    for (int i = id; i; i -= lowbit(i)) sum += tree[i];
    return sum;
  }

  T get_sum(int l, int r) { return get_sum(r) - get_sum(l - 1); }

 private:
  int n;
  vector<T> tree;
  int lowbit(int x) { return x & -x; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  ll maxi = -inf;
  n = in();
  vll a(n + 1), big(n + 1), low(n + 1);
  for (int i = 1; i <= n; i++) maxi = max(a[i] = in(), maxi);
  Array_tree<ll> tr(maxi);
  for (int i = 1; i <= n; i++) {
    int x = a[i];
    big[i] = tr.get_sum(x + 1, n);
    low[i] = tr.get_sum(x - 1);
    tr.add(x, 1);
  }
  ll ans1 = 0, ans2 = 0;
  tr = Array_tree<ll>(maxi);
  for (int i = n; i > 0; i--) {
    int x = a[i];
    ans1 += big[i] * tr.get_sum(x + 1, n);
    ans2 += low[i] * tr.get_sum(x - 1);
    tr.add(x, 1);
  }
  cout << ans1 << " " << ans2 << endl;

  return;
}



QQ232
1个月前

css代码

.QQ-game-menu {
    width: 100%;
    height: 100%;
    background-image: url("/static/image/menu/background.gif");
    background-size: 100% 100%;
    user-select: none;
}

.QQ-game-menu-field {
    width: 20vw;
    position: relative;
    top: 40vh;
    left: 19vw;
}

.QQ-game-menu-field-item {
    text-align: center;
    color: white;
    height: 7vh;
    width: 18vw;
    font-size: 6vh;
    padding: 2vh;
    background-color: rgba(39, 21, 28, 0.6);
    border-radius: 10px;
    letter-spacing: 0.5vw;
    cursor:pointer;
    font-style: italic;
}

.QQ-game-menu-field-item:hover {
    transform: scale(1.2);
    transition: 100ms;
}

js代码

class QQGameMenu {
    constructor (root) {
        this.root = root;
        this.$menu = $(`
<div class="QQ-game-menu">
    <div class="QQ-game-menu-field">
        <div class="QQ-game-menu-field-item QQ-game-menu-field-item-single">
            单人模式
        </div>
        <div class="QQ-game-menu-field-item QQ-game-menu-field-item-multi">
            多人模式
        </div>
        <div class="QQ-game-menu-field-item QQ-game-menu-field-item-settings">
            设置
        </div>
    </div>
</div>
`);
        this.root.$QQ_game.append(this.$menu);
        this.$single = this.$menu.find('.QQ-game-menu-field-item-single');
        this.$multi = this.$menu.find('.QQ-game-menu-field-item-multi');
        this.$settings = this.$menu.find('.QQ-game-menu-field-item-settings');
        this.start();
    }

    start() {
        this.add_listening_events();
    }

    add_listening_events() {
        let outer = this;
        this.$single.click(function(){
            outer.hide();
            outer.root.playground.show();
        });
        this.$multi.click(function(){
            console.log("click multi mode");
        });
        this.$settings.click(function(){
            console.log("click settings");
        });
    }

    show() {  // 显示menu界面
        this.$menu.show();
    }


    hide() {  // 关闭menu界面
       this.$menu.hide();
    }

}

class QQGamePlayground {
        constructor(root) {
            this.root = root;
            this.$playground = $(`<div>游戏界面</div>`);
            this.hide();
            this.root.$QQ_game.append(this.$playground);
            this.start();
        }
        start() {}

        show() {  // 打开playground界面
            this.$playground.show();
        }

        hide() {  // 关闭playground界面
            this.$playground.hide();
        }
}

class QQgame {
    constructor(id){
        this.id = id;
        this.$QQ_game = $('#' + id);
        this.menu = new QQGameMenu(this);
        this.playground = new QQGamePlayground(this);
        this.start();
    }
    start() {}
}





QQ232
1个月前

算法1

(杀鸡用牛刀之主席树)

用主席树板子做线段树, 主要为了调试板子

时间复杂度

$O(n*logn)$

参考文献

C++ 代码

#include <bits/stdc++.h>
#define endl '\n'
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>
#define x first
#define y second
#define ALL(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
inline ll in() {
  register ll s = 0, w = 1, 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;
}
void solve();
ll n, m;

template <class T>
class HJT_tree {
  //处理数据默认下标从1开始
 public:
  //构造函数
  HJT_tree() {}
  HJT_tree(vector<T> v) {
    base = v, this->n = base.size() - 1;
    tree = vector<node>(n * 32), root.push_back(build(1, n));
  }

  void updata(int v, int x, T value) {
    //插入函数(版本,修改位置,修改值)
    root.push_back(insert(root[v], 1, n, x, value));
  }

  T query(int v, int x) {
    //查询函数(版本,查询位置)
    return get_se(root[v], 1, n, x, x);
  }

  T query(int v, int l, int r) {
    //查询函数(版本,查询区间)
    return get_se(root[v], 1, n, l, r);
  }

 private:
  vi root;
  vector<T> base;
  int n, idx = 0;
  struct node {
    int l, r;
    T data;
  };
  vector<node> tree;
  void pushup(int q) { tree[q].data = op(tree[q].l, tree[q].r); }
  T op(int l, int r) { return max(tree[l].data, tree[r].data); }
  T e() { return -inf; }
  int build(int l, int r) {
    int now = ++idx, mid = l + r >> 1;
    if (l != r)
      tree[now].l = build(l, mid), tree[now].r = build(mid + 1, r), pushup(now);
    return now;
  }
  int insert(int old, int l, int r, int x, int value) {
    int now = ++idx, mid = l + r >> 1;
    tree[now] = tree[old];
    if (l == r)
      tree[now].data = value;
    else {
      if (x <= mid)
        tree[now].l = insert(tree[old].l, l, mid, x, value);
      else
        tree[now].r = insert(tree[old].r, mid + 1, r, x, value);
      pushup(now);
    }
    return now;
  }
  T get_se(int v, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[v].data;
    ll mid = l + r >> 1;
    T res = e();
    if (L <= mid) res = max(res, get_se(tree[v].l, l, mid, L, R));
    if (R > mid) res = max(res, get_se(tree[v].r, mid + 1, r, L, R));
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  cin >> n >> m;
  HJT_tree<ll> tr(vll(n + 1));
  ll r = 0, t = 0;
  for (ll i = 1, x; i <= n; i++) {
    char op[2];
    cin >> op >> x;
    if (op[0] == 'A') {
      int old = r++;
      tr.updata(old, r, (x + t) % m);
    } else {
      t = tr.query(r, r - x + 1, r);
      cout << t << endl;
    }
  }
  return;
}


活动打卡代码 AcWing 803. 区间合并

QQ232
1个月前
#include <bits/stdc++.h>
#define endl '\n'
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>
#define x first
#define y second
#define ALL(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
inline ll in() {
  register ll s = 0, w = 1, 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;
}
void solve();
ll n, m;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  cin >> n;
  auto merge = [&](vector<pll> sg) {
    //区间合并
    vector<pll> res;
    sort(ALL(sg));
    ll st = -inf, en = -inf;
    for (auto i : sg) {
      if (en < i.x) {
        if (st != -inf) res.push_back({st, en});
        st = i.x, en = i.y;
      } else
        en = max(en, i.y);
    }
    if (st != -inf) res.push_back({st, en});
    return res;
  };
  vector<pll> v;
  for (int i = 1, l, r; i <= n; i++) {
    cin >> l >> r;
    v.push_back({l, r});
  }
  cout << merge(v).size() << endl;
  return;
}


活动打卡代码 AcWing 255. 第K小数

QQ232
1个月前
#include <bits/stdc++.h>
#define endl '\n'
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>
#define x first
#define y second
#define ALL(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
inline ll in() {
  register ll s = 0, w = 1, 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;
}
void solve();
ll n, m;
vll v;

int find(int x) { return lower_bound(ALL(v), x) - v.begin(); }

template <class T>
class HJT_tree {  //处理数据默认下标从1开始
 public:
  vi root;
  HJT_tree() {}
  HJT_tree(vector<T> v) {
    this->n = v.size() - 1, tree = vector<node>(n * 32);
    root.push_back(build(1, n));
    for (int i = 1; i <= n; i++)
      root.push_back(insert(root[i - 1], 1, n, find(v[i])));
  }

  HJT_tree(T a[], int n) {
    this->n = n, tree = vector<node>(n * 40);
    root.push_back(build(1, n));
    for (int i = 1; i <= n; i++)
      root.push_back(insert(root[i - 1], 1, n, find(a[i])));
  }

  int insert(int old, int l, int r, int value) {
    int now = ++idx;
    tree[now] = tree[old];
    if (l == r) {
      tree[now].data++;
      return now;
    }
    int mid = l + r >> 1;
    if (value <= mid)
      tree[now].l = insert(tree[old].l, l, mid, value);
    else
      tree[now].r = insert(tree[old].r, mid + 1, r, value);
    pushup(now);
    return now;
  }

  int query(int old, int now, int l, int r, int k) {
    if (l == r) return r;
    T cnt = tree[tree[now].l].data - tree[tree[old].l].data;
    //cout << cnt << " " << k << " " << l << " " << r << endl;
    int mid = l + r >> 1;
    if (k <= cnt)
      return query(tree[old].l, tree[now].l, l, mid, k);
    else
      return query(tree[old].r, tree[now].r, mid + 1, r, k - cnt);
  }

 private:
  int n, idx = 0;
  struct node {
    int l, r;
    T data;
  };
  vector<node> tree;
  void pushup(int q) { tree[q].data = op(tree[q].l, tree[q].r); }
  T op(int l, int r) { return tree[l].data + tree[r].data; }
  int build(int l, int r) {
    int now = ++idx;
    if (l == r) return now;
    int mid = l + r >> 1;
    tree[now].l = build(l, mid);
    tree[now].r = build(mid + 1, r);
    return now;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

void solve() {
  int cnt = 0;
  n = in(), m = in();
  vll a(n + 1);
  v.push_back(-inf);
  for (int i = 1; i <= n; i++) a[i] = in(), v.push_back(a[i]);
  sort(ALL(v));
  v.erase(unique(ALL(v)), v.end());
  HJT_tree<ll> tr(a);
  while (m--) {
    int l = in(), r = in(), k = in();
    cout << v[tr.query(tr.root[l - 1], tr.root[r], 1, n, k)] << endl;
  }
  return;
}


活动打卡代码 AcWing 368. 银河

QQ232
1个月前
#include <bits/stdc++.h>
#define u_set unordered_set
#define u_map unordered_map
#define vi vector<int>
#define pll pair<long long, long long>
#define vll vector<long long>
#define pii pair<int, int>

using namespace std;
typedef long long ll;

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int maxm = 3e5 + 10;

int n, m, st, en, cnt = 0;
int path[maxn], bj[maxn], head[maxn];
ll dis[maxn];
struct node {
  int id;
  ll dis;
  node(int i, ll j) : id(i), dis(j) {}
  friend bool operator<(node a, node b) { return a.dis > b.dis; }
};

struct edge {
  int to, next;
  ll w;
} e[maxm];

void add(int u, int v, ll w) {
  e[++cnt].to = v, e[cnt].w = w, e[cnt].next = head[u], head[u] = cnt;
}

bool SPFA(int st) {
  vector<ll>num(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    bj[i] = 0, dis[i] = -inf;
  }
  stack<int> q;
  dis[st] = 0;
  bj[st] = 1;
  q.push(st);
  while (!q.empty()) {
    int u = q.top();
    q.pop();
    bj[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to;
      if (dis[v] < dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        num[v] = num[u] + 1;
        if(num[v] >= n + 1) return false;
        if (!bj[v]) {
          bj[v] = 1, q.push(v);
        }
      }
    }
  }
  return true;
}

void solve();

int main() {
  solve();
  return 0;
}

void solve() {
  cin >> n >> m;
  for (int x, u, v, i = 1; i <= m; i++) {
    cin >> x >> u >> v;
    if (x == 1)
      add(u, v, 0), add(v, u, 0);
    else if (x == 2)
      add(u, v, 1);
    else if (x == 3)
      add(v, u, 0);
    else if (x == 4)
      add(v, u, 1);
    else if (x == 5)
      add(u, v, 0);
  }
  for(int i = 1; i <= n; i++) {
    add(0, i, 1);
  }
  if(!SPFA(0)) {
    cout <<"-1\n";
  }else {
    ll ans = 0;
    for(int i = 1; i <= n; i++) ans += dis[i];
    cout << ans;
  }
  return;
}