都是神题，一道都搞不出来
#include<bits/stdc++.h> using namespace std; #define ll long long const int M = 5 * 1e5 + 10; int a[M], n, c[M], b[M]; struct node{int l, r;}; queue <node> q; vector <node> p[M]; int Max(int x, int y){ if(!x) return y; if(!y) return x; if(a[x] > a[y]) return x; return y; } struct Node { int v; Node *ls , *rs; void up(){ v = Max(ls->v, rs->v); } }pool[M << 2], *root, *tail = pool; #define Ls l, mid, nd->ls #define Rs mid+1, r, nd->rs Node *build(int l = 1, int r = n){ Node * nd = ++tail; if(l == r)nd->v = l; else { int mid = (l + r) >> 1; nd->ls = build(l, mid); nd->rs = build(mid + 1, r); nd->up(); } return nd; } int query(int L, int R, int l = 1, int r = n, Node * nd = root){ if(l >= L && R >= r) return nd->v; else { int mid = (l + r) >> 1; int y = 0, z = 0; if(L <= mid)z = query(L, R, Ls); if(R > mid) y = query(L, R, Rs); return Max(z, y); } } inline int lowbit(int x){return x & (-x);} void add(int x){ for(; x <= n; x += lowbit(x)) c[x]++; } int Query(int x){ int ret = 0; for(; x; x -= lowbit(x)) ret += c[x]; return ret; } int main(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); long long ans = 0; scanf("%d", &n); for(int i=1;i<=n;i++)scanf("%d", &a[i]); root = build(); q.push((node){1, n}); while(!q.empty()){ int l = q.front().l, r = q.front().r; q.pop(); if(l > r)continue; int mid = query(l, r); q.push((node){l, mid - 1}); q.push((node){mid + 1, r}); if(mid - l < r - mid){ for(int i = l; i <= mid; i++) { p[mid - 1].push_back((node){a[mid] / a[i], -1}); p[r].push_back((node){a[mid] / a[i], 1}); } } else { for(int i = mid; i <= r; i++) { p[l - 1].push_back((node){a[mid] / a[i], -1}); p[mid].push_back((node){a[mid] / a[i], 1}); } } //printf("%d %d %d ", l, r, mid); } for(int i = 1; i <= n; i++) b[i] = a[i]; sort(b + 1, b + 1 + n); int s = unique(b + 1, b + 1 + n) - b - 1; for(int i = 1; i <= n; i++){ if(a[i] <= 1) ans--; int pos = lower_bound(b + 1, b + 1 + s, a[i]) - b; add(pos); for(int j = 0; j < p[i].size(); j++){ int lim = upper_bound(b + 1, b + 1 + s, p[i][j].l) - b - 1; int tot = Query(lim); int pt = p[i][j].r; if(p[i][j].r > 0) ans += tot; else ans -= tot; //printf("%d %d %d %lld ", i, lim, pt, ans); } } printf("%lld ", ans); }
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int M = 1e5+5; #define ll long long int a[M], tmp[M]; int main(){ freopen("B.in","r",stdin); freopen("B.out","w",stdout); ll m, n; scanf("%lld%lld", &n, &m); m--; for(int i=0;i<n;i++)scanf("%d", &a[i]); for(ll i=0;i<=60;i++){ if((m>>i) & 1){ //printf("%d ", i); ll d = 1LL<<i; for(ll j=0;j<n;j++) tmp[j] = a[j] ^ a[(j + d) % n]; for(ll j=0;j<n;j++) a[j] = tmp[j]; } } for(int i=0;i<n;i++)printf("%d ", a[i]); }
#include<bits/stdc++.h> using namespace std; const int M = 1e5 + 10; struct col{int t, c;}; map <int,int> vis; vector <col> b[M]; int a[M], h[M], n, tot, siz[M], ans[M], ix, idc, fin[M]; struct edge{int v,nxt;}G[M<<1]; void add(int u, int v){G[++tot].v=v,G[tot].nxt=h[u],h[u]=tot;} struct Node { int tag, sum1, sum2; Node *ls , *rs; void down(){ if(tag){ ls->sum1 = ls->sum2 = rs->sum1 = rs->sum2 = 0; ls->tag = rs->tag = 1; tag = 0; } } }pool[M << 2], *root, *tail = pool; Node *build(int l = 1, int r = n){ Node * nd = ++tail; if(l == r); else { int mid = (l + r) >> 1; nd->ls = build(l, mid); nd->rs = build(mid + 1, r); } return nd; } #define Ls l, mid, nd->ls #define Rs mid+1, r, nd->rs void insert(int pos, int d1, int d2, int l = 1, int r = n, Node * nd = root){ nd->sum1 += d1, nd->sum2 += d2; if(l == r) return; else { nd->down(); int mid = (l + r) >> 1; if(pos <= mid)insert(pos, d1, d2, Ls); else insert(pos, d1, d2, Rs); } } int query(int pos, int l = 1, int r = n, Node * nd = root){ if(l == r) return l; else { nd->down(); int mid = (l + r) >> 1; if(pos <= nd->ls->sum2) return query(pos, Ls); return query(pos - nd->ls->sum2, Rs); } } int query_sum(int L, int R, int l = 1, int r = n, Node * nd = root){ if(l >= L && r <= R) return nd->sum1; int mid = (l + r) >> 1; nd->down(); int ans = 0; if(L <= mid)ans += query_sum(L, R, Ls); if(R > mid) ans += query_sum(L, R, Rs); return ans; } #define ex(i, u) for(int i = h[u]; i; i = G[i].nxt) void dfs1(int u, int f){ siz[u] = 1; ex(i, u){ int v=G[i].v; if(v==f)continue; dfs1(v, u); siz[u]+=siz[v]; } } void unget(int u){ int len = b[u].size(); for(int i = 0; i < len; i++) fin[b[u][i].c] = 0; } void get(int u){ int len = b[u].size(); for(int i = 0; i < len; i++){ int c = b[u][i].c, t = b[u][i].t; insert(t, 0, 1); if(!fin[c]){ fin[c] = t; insert(t, 1, 0); } else if(t < fin[c]){ insert(fin[c], -1, 0); fin[c] = t; insert(t, 1, 0); } } } void dfs2(int u, int f, int fg){ int son = 0; ex(i, u){ int v=G[i].v; if(v == f)continue; if(siz[v] > siz[son])son = v; } ex(i, u){ int v=G[i].v; if(v == f||v == son)continue; dfs2(v, u, 1); } if(son) dfs2(son, u, 0); get(u); ex(i, u){ int v=G[i].v; if(v == f||v == son)continue; get(v); } if(!a[u]) ans[u] = 0; else { ans[u] = root->sum1; if(ans[u] > a[u]){ int t=query(a[u]); ans[u] = query_sum(1, t); } } if(son){ b[u].swap(b[son]); ex(i, u){ int v=G[i].v; if(v == f)continue; b[u].insert(b[u].end(), b[v].begin(), b[v].end()); } } if(fg){ root->tag=1; root->sum1=root->sum2=0; unget(u); } //printf("%d %d ", u, ans[u]); } int main(){ freopen("ac.in","r",stdin); freopen("ac.out","w",stdout); scanf("%d", &n); int u, v, m, Q; for(int i = 1; i < n; i++){ scanf("%d%d", &u, &v); add(u, v); add(v, u); } for(int i=1;i<=n;i++)scanf("%d", &a[i]); scanf("%d", &m); int x, c; for(int i=1;i<=m;i++){ scanf("%d%d", &x, &c); if(!vis[c]) vis[c] = ++ix; b[x].push_back((col){i, vis[c]}); } dfs1(1, 0); root = build(); root->tag = 1; root->sum1=root->sum2 = 0; dfs2(1, 0, 0); scanf("%d", &Q); while(Q--){ scanf("%d", &x); printf("%d ", ans[x]); } }