contents：
A Simple Problem with Integers
链接: link.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int, int>
#define psi pair<string, int>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define ld long double
const int N = 1E5 + 7;
#define INF ~0ULL
ll a[N], sum[N], add[N]; //原，区间和，增量标记
int L[N], R[N]; //每段左右标记
int pos[N]; //每个位置属于那一段
int n, m, block;
void change(int l, int r, ll d) //区间加
{
int p = pos[l], q = pos[r];
if (p == q)
{
for (int i = l; i <= r; i++)
a[i] += d;
sum[p] += d * (r - l + 1);
}
else
{
for (int i = p + 1; i <= q - 1; i++)
add[i] += d;
for (int i = l; i <= R[p]; i++)
a[i] += d;
sum[p] += d * (R[p] - l + 1);
for (int i = L[q]; i <= r; i++)
a[i] += d;
sum[q] += d * (r - L[q] + 1);
}
}
ll ask(int l, int r) //区间询问
{
int p = pos[l], q = pos[r];
ll ans = 0;
if (p == q)
{
for (int i = l; i <= r; i++)
ans += a[i];
ans += add[p] * (r - l + 1);
}
else
{
for (int i = p + 1; i <= q - 1; i++)
ans += sum[i] + add[i] * (R[i] - L[i] + 1);
for (int i = l; i <= R[p]; i++)
ans += a[i];
ans += add[p] * (R[p] - l + 1);
for (int i = L[q]; i <= r; i++)
ans += a[i];
ans += add[q] * (r - L[q] + 1);
}
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
block = sqrt(n);
for (int i = 1; i <= block; i++)
{
L[i] = (i - 1) * block + 1;
R[i] = i * block;
}
if (R[block] < n)
block++, L[block] = R[block - 1] + 1, R[block] = n;
//预处理
for (int i = 1; i <= block; i++)
{
for (int j = L[i]; j <= R[i]; j++)
{
pos[j] = i;
sum[i] += a[j];
}
}
//指令
while (m--)
{
char op[3];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (op[0] == 'C')
{
scanf("%d", &d);
change(l,r,d);
}
else printf("%lld\n",ask(l,r));
}
return 0;
}
蒲公英
链接: link.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <functional>
using namespace std;
const int N = 1e5 + 10;
const int T = 500;
int n, m, block; //数组长度，询问次数，块数量
int a[N], b[N], f[N], tot; //原，属于哪个段，
int d[1000][1000]; //从start到后面的数量
int g[T][N];
int ct[N];
int num[N], tmp[N];
void build()
{
block = (int)sqrt(1.0 * n);
for (int i = 1; i <= n; i++)
b[i] = (i - 1) / block + 1; //属于哪个段数
}
void pre(int x) //预处理x到后面的众数
{
int top = 0;
int mx = -1, ans = 0;
for (int i = (x - 1) * block + 1; i <= n; i++)
{
g[x][a[i]]++;
ct[a[i]]++;
if (ct[a[i]] == 1)
{
tmp[++top] = a[i]; //这里我是想省去memset的时间
}
if (ct[a[i]] > mx || (ct[a[i]] == mx && a[i] < ans))
{
ans = a[i];
mx = ct[a[i]];
}
d[x][b[i]] = ans;
}
while (top)
{
ct[tmp[top--]] = 0;
; //这里我是想省去memset的时间
}
}
int query(int l, int r)
{
int p = b[l], q = b[r];
int ans = 0, cnt = 0, top = 0;
int up = b[l] * block;
if (q - p < 2)
{
for (int i = l; i <= r; i++)
{
++ct[a[i]];
if (ct[a[i]] == 1)
{
tmp[++top] = a[i];
}
}
while (top)
{
int x = tmp[top--];
if (cnt < ct[x] || (cnt == ct[x] && x < ans))
{
ans = x;
cnt = ct[x];
}
ct[x] = 0;
}
return ans;
}
for (int i = l; i <= up; i++)
{
++ct[a[i]];
if (ct[a[i]] == 1)
{
tmp[++top] = a[i];
num[a[i]] = g[p + 1][a[i]] - g[q][a[i]];
}
}
for (int i = (b[r] - 1) * block + 1; i <= r; i++)
{
++ct[a[i]];
if (ct[a[i]] == 1)
{
tmp[++top] = a[i];
num[a[i]] = g[p + 1][a[i]] - g[q][a[i]];
}
}
ans = d[b[l] + 1][b[r] - 1];
num[ans] = g[p + 1][ans] - g[q][ans]; //这个一定别忘了，因为ans可能未在旁边两块出现过。
cnt = ct[ans] + num[ans];
while (top)
{
int x = tmp[top--];
ct[x] += num[x];
if (cnt < ct[x] || (cnt == ct[x] && x < ans))
{
ans = x;
cnt = ct[x];
}
ct[x] = 0;
num[x] = 0;
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
f[i] = a[i];
}
build();
sort(f + 1, f + n + 1);
int N = unique(f + 1, f + n + 1) - f - 1;
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(f + 1, f + N + 1, a[i]) - f;
}
for (int i = 1; i <= b[n]; i++)
pre(i);
int ans = 0;
while (m--)
{
int l, r;
scanf("%d%d", &l, &r);
l = (l + ans - 1) % n + 1;
r = (r + ans - 1) % n + 1;
if (l > r)
swap(l, r);
ans = f[query(l, r)];
printf("%d\n", ans);
}
return 0;
}
磁力块
链接: link.
小Z的袜子
链接: link.
别人的学习笔记
链接: link.