2018-07-03
统计l到r之间有几个数字。莫队裸题
/*
* Author: JiangYu
* Created Time: 2018/6/29 23:07:03
* File Name: A.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 2e5 + 1024;
struct query{
int l, r, id;
}q[N];
int a[N], b[N];
int n, m, P;
bool cmp(const query &o, const query &t) {
if(o.l / P == t.l / P) return o.r < t.r;
return o.l / P < t.l / P;
}
int tmp;
int num[N],ans[N];
void add(int x) {
if(!num[x]) tmp++;
num[x]++;
}
void del(int x) {
num[x]--;
if(!num[x]) tmp--;
}
void solve() {
P = (int) sqrt(n);
sort(q+1, q+1+m, cmp);
int l = 1, r = 0;
tmp = 0;
for(int i = 1; i <= m; ++i) {
while(r < q[i].r) {
++r;
add(a[r]);
}
while(r > q[i].r) {
del(a[r]);
r--;
}
while(l < q[i].l) {
del(a[l]);
l++;
}
while(l > q[i].l) {
--l;
add(a[l]);
}
ans[q[i].id] = tmp;
}
for(int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n);
for(int i = 1; i <= n; ++i) {
a[i] = lower_bound(b+1, b+1+n, a[i]) - b;
}
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
solve();
return 0;
}
统计l到r的值,值的定义为 $(number_k) ^ 2 * k$ 之和。依旧是莫队裸题
/*
* Author: JiangYu
* Created Time: 2018/6/29 23:07:03
* File Name: B.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e6 + 1024;
struct query{
int l, r, id;
}q[N];
int a[N], b[N];
int n, m, P;
bool cmp(const query &o, const query &t) {
if(o.l / P == t.l / P) return o.r < t.r;
return o.l / P < t.l / P;
}
ll tmp;
int num[N];
ll ans[N];
void add(int x) {
//cout << "+" << x;
tmp -= 1ll*x*num[x]*num[x];
num[x]++;
tmp += 1ll*x*num[x]*num[x];
}
void del(int x) {
//cout << "-"<<x;
tmp -= 1ll*x*num[x]*num[x];
num[x]--;
tmp += 1ll*x*num[x]*num[x];
}
void solve() {
P = (int) sqrt(n);
sort(q+1, q+1+m, cmp);
int l = 1, r = 0;
tmp = 0;
for(int i = 1; i <= m; ++i) {
while(r < q[i].r) {
++r;
add(a[r]);
//cout << "+" << a[r];
}
while(r > q[i].r) {
//cout << "-" << a[r];
del(a[r]);
r--;
}
while(l < q[i].l) {
//cout << "-" << a[l];
del(a[l]);
l++;
}
while(l > q[i].l) {
--l;
add(a[l]);
//cout << "+"<<a[l];
}
ans[q[i].id] = tmp;
}
//for(int i = 1; i <= n; ++i)
//cout << num[i]<<" ";
for(int i = 1; i <= m; ++i) {
printf("%I64d\n", ans[i]);
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
solve();
return 0;
}
统计l,r两点之间有多少个联通块。不会……
统计l到r之间有多少个不同的子串。也是莫队,但是更新好像要用后缀数组搞,暂时不会,先空着(八成永远空着了)。
一个树,统计l点到r点之间,出现k次以上的颜色的数量。 第一步肯定是根据dfs序,将这颗树拆成线段。 然后,因为数据量不大,有两种做法。 其一是莫队+树状数组,加了一个log,但是很好理解。
/*
* Author: JiangYu
* Created Time: 2018/6/30 15:34:59
* File Name: E.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5 + 1024;
int n, m;
int in[N], out[N], is[N], times;
bool vis[N];
vector<int> g[N];
int P;
struct node{
int l, r, k, id;
}q[N];
bool cmp(const node & o, const node &t) {
if(o.l / P == t.l / P) return o.r < t.r;
return o.l < t.l;
}
int a[N];
int tmp, num[N];
int num_num[N];
int ans[N];
struct BIT {
int bit[N];
void init() {
memset(bit, 0, sizeof bit);
}
int lowbit(int k) {
return k & -k;
}
void add(int x, int y) {
//cout << x<< ":";
//cout << 0 + lowbit(0);
if(x <= 0) return;
while(x < N) {
bit[x] += y;
x += lowbit(x);
}
}
int sum(int x) {
int res = 0;
if(x <= 0) return 0;
while(x) {
res += bit[x];
x -= lowbit(x);
}
return res;
}
}bit;
void add(int x) {
num[x]++;
bit.add(num[x], 1);
bit.add(num[x] - 1, -1);
}
void del(int x) {
num[x]--;
bit.add(num[x] + 1, -1);
bit.add(num[x], 1);
}
void solve() {
int l = 1, r = 0;
for(int i = 1; i <= m; ++i) {
//cout << "-";
while(r < q[i].r) {
r++;
add(a[is[r]]);
}
//cout << "=";
while(r > q[i].r) {
del(a[is[r]]);
r--;
}
//cout << "+";
while(l > q[i].l) {
--l;
add(a[is[l]]);
}
//cout << ")";
while(l < q[i].l) {
del(a[is[l]]);
++l;
}
//cout << "??";
ans[q[i].id] = bit.sum(N-1) - bit.sum(q[i].k - 1);
//cout << endl;
}
for(int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
}
void dfs(int u) {
in[u] = ++times;
is[times] = u;
vis[u] = 1;
for(auto v : g[u]) {
if(vis[v]) continue;
dfs(v);
}
out[u] = times;
}
int main() {
scanf("%d%d", &n, &m);
bit.init();
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n-1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[u].PB(v);
g[v].PB(u);
}
dfs(1);
P = (int) sqrt(n);
for(int i = 1; i <= m; ++i) {
int u, k;
scanf("%d%d", &u, &k);
q[i].l = in[u];
q[i].r = out[u];
q[i].id = i;
q[i].k = k;
}
sort(q+1, q+1+m, cmp);
solve();
return 0;
}
其二是考虑新开一个计数数组,当某一个颜色加1时,就在那个计数数组对应数量的地方加一,再次出现这个颜色也会在新的对应数量的地方加一。 一路加上去就好。减少某一个颜色也是这个做法,一路减下去。因为莫队的方式,每次都是在端点更新,所以可以把做法一的树状数组压缩到O(n)。 时间只需要原来的1/3
/*
* Author: JiangYu
* Created Time: 2018/6/30 15:34:59
* File Name: E.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5 + 1024;
int n, m;
int in[N], out[N], is[N], times;
bool vis[N];
vector<int> g[N];
int P;
struct node{
int l, r, k, id;
}q[N];
bool cmp(const node & o, const node &t) {
if(o.l / P == t.l / P) return o.r < t.r;
return o.l < t.l;
}
int a[N];
int tmp, num[N];
int num_num[N];
int ans[N];
void add(int x) {
//cout << " + " << x;
num[x]++;
num_num[num[x]]++;
}
void del(int x) {
//cout << "-" << x;
num_num[num[x]]--;
num[x]--;
}
void solve() {
int l = 1, r = 0;
for(int i = q[1].l; i <= q[1].r; ++i) {
num[a[is[i]] ]++;
num_num[ num[a[is[i]] ] ] ++;
}
ans[q[1].id] = num_num[q[1].k];
l = q[1].l, r = q[1].r;
//for(int i = 1; i <= n; ++i) {
//cout << num_num[i] << " ";
//}
//cout << endl;
for(int i = 2; i <= m; ++i) {
//cout << "-";
//cout << q[i].l << " " << q[i].k << " " << q[i].id <<endl;
while(r < q[i].r) {
r++;
add(a[is[r]]);
}
//cout << "=";
while(r > q[i].r) {
del(a[is[r]]);
r--;
}
//cout << "+";
while(l > q[i].l) {
--l;
add(a[is[l]]);
}
//cout << ")";
while(l < q[i].l) {
del(a[is[l]]);
++l;
}
//cout << "??";
ans[q[i].id] = num_num[q[i].k];
//cout << endl;
}
for(int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
}
void dfs(int u) {
in[u] = ++times;
is[times] = u;
vis[u] = 1;
for(auto v : g[u]) {
if(vis[v]) continue;
dfs(v);
}
out[u] = times;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n-1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[u].PB(v);
g[v].PB(u);
}
dfs(1);
P = (int) sqrt(n);
for(int i = 1; i <= m; ++i) {
int u, k;
scanf("%d%d", &u, &k);
q[i].l = in[u];
q[i].r = out[u];
q[i].id = i;
q[i].k = k;
}
sort(q+1, q+1+m, cmp);
solve();
return 0;
}
在l到r区间内,看是否存在某一个数组,下标全为等差数列。 存在答案即为区间内数字的种数,否则为种数加一。 我们可以预处理出fl[i], fr[i]. 表示i这个数字往左(往右)数,第一个下标不属于等差数列的位置。 然后就是普通莫队了。
/*
* Author: JiangYu
* Created Time: 2018/6/30 17:36:04
* File Name: F.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5 + 1024;
struct node {
int l, r, id;
} q[N];
int n, a[N];
int P;
int last[N], pre[N], bac[N];
bool cmp(const node &o, const node &t) {
if(o.l / P == t.l / P) return o.r < t.r;
return o.l < t.l;
}
int num[N], cnt, tmp;
int m, fl[N], fr[N];
int ans[N];
void add1(int pos, int l) {
num[a[pos]]++;
if(num[a[pos]] == 1) {
cnt++;
tmp++;
}
else if(fl[pos] >= l && fl[pre[pos]] < l) cnt--;
}
void del1(int pos, int l) {
num[a[pos]]--;
if(num[a[pos]] == 0) {
cnt--;
tmp--;
}
else if(fl[pos] >= l && fl[pre[pos]] < l) cnt++;
}
void add2(int pos, int r) {
num[a[pos]]++;
if(num[a[pos]] == 1) {
cnt++;
tmp++;
}
else if(fr[pos] <= r && fr[bac[pos]] > r) cnt--;
}
void del2(int pos, int r) {
num[a[pos]]--;
if(num[a[pos]] == 0) {
cnt--;
tmp--;
}
else if(fr[pos] <= r && fr[bac[pos]] > r) cnt++;
}
void solve() {
int l = 1, r = 0;
for(int i = 1; i <= m; ++i) {
while( r < q[i].r) {
r++;
add1(r, l);
}
while( r > q[i].r) {
del1(r, l);
r--;
}
while( l < q[i].l) {
del2(l, r);
l++;
}
while( l > q[i].l) {
l--;
add2(l, r);
}
if(cnt > 0)
ans[q[i].id] = tmp;
else
ans[q[i].id] = tmp + 1;
}
for(int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
}
int main() {
scanf("%d", &n);
P = sqrt(n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i) {
pre[i] = last[a[i]];
last[a[i]] = i;
if (pre[ pre[i] ] == 0)
fl[i] = 0;
else if (pre[i] - pre[pre[i]] == i - pre[i])
fl[i] = fl[pre[i]];
else
fl[i] = pre[pre[i]];
}
CLR(last);
for(int i = n; i >= 1; --i) {
bac[i] = last[a[i]];
last[a[i]] = i;
if(bac[ bac[i] ] == 0)
fr[i] = n+1;
else if (bac[ bac[i] ] - bac[i] == bac[i] - i)
fr[i] = fr[ bac[i] ];
else
fr[i] = bac[ bac[i] ];
}
scanf("%d", &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q+1, q+1+m, cmp);
solve();
return 0;
}
统计l到r区间内的逆序对数量, 莫队加一个树状数组统计就好了。
/*
* Author: JiangYu
* Created Time: 2018/7/2 11:48:29
* File Name: G.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5;
struct node{
int l, r, id;
}q[N];
int n, m, P;
int a[N], b[N];
bool cmp(const node &o, const node &t) {
if(o.l / P == t.l / P) return o.r < t.r;
return o.l < t.l;
}
struct BIT {
int tree[N];
int n;
void init(int nn) {
memset(tree, 0, sizeof tree);
n = nn + 1;
}
int lowbit(int k) {
return k & -k;
}
void add(int x, int y) {
while(x < n) {
tree[x] += y;
x += lowbit(x);
}
}
int sum(int x) {
int res = 0;
while(x) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
}bit;
int tmp, ans[N];
void add(int pos) {
tmp += bit.sum(b[pos]-1);
bit.add(b[pos], 1);
}
void del(int pos) {
tmp -= bit.sum(b[pos]-1);
bit.add(b[pos], -1);
}
void add2(int pos, int l) {
tmp += (pos - l - bit.sum(b[pos]));
bit.add(b[pos], 1);
}
void del2(int pos, int l) {
tmp -= (pos - l - bit.sum(b[pos]) + 1);
bit.add(b[pos], -1);
}
void solve() {
int l = 1, r = 0;
for(int i = 1; i <= m; ++i) {
while(r < q[i].r) {
r++;
add2(r, l);
}
while(r > q[i].r) {
del2(r, l);
r--;
}
while(l < q[i].l) {
del(l);
l++;
}
while(l > q[i].l) {
l--;
add(l);
}
ans[q[i].id] = tmp;
}
for(int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
}
int main() {
cin >> n;
bit.init(n);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
b[i] = a[i];
}
sort(a+1, a+1+n);
for(int i = 1; i <= n; ++i) {
b[i] = lower_bound(a+1, a+1+n, b[i]) - a;
}
P = sqrt(n);
cin >> m;
for(int i = 1; i <= m; ++i) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q+1, q+1+m, cmp);
solve();
return 0;
}