## 【日常小测】友好城市

### Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ];
struct Query{
int l, r, blk, id;
inline bool operator < (const Query &Q) const {
return blk < Q.blk || (blk == Q.blk && r < Q.r);
}
}qy[QQ];
struct Bitset{
UI v[5];
inline void flip(int x) {
v[x >> 5] ^= 1 << (x & 31);
}
inline void set(int x) {
v[x >> 5] |= 1 << (x & 31);
}
inline void reset() {
memset(v, 0, sizeof(v));
}
inline bool operator [](int x) {
return v[x >> 5] & (1 << (x & 31));
}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
a1[u].set(v);
a2[v].set(u);
}

class Kosaraju{
vector<int> que;
Bitset vis;
public:
inline int solve() {
vis.reset();
que.clear();
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs0(i);
}
}
vis.reset();
int ret = 0;
for (int j = n - 1; ~j; j--) {
int i = que[j];
if (!vis[i]) {
int cnt = dfs1(i);
ret += cnt * (cnt - 1) / 2;
}
}
return ret;
}
private:
inline void dfs0(int w) {
vis.flip(w);
for (int i = 0; i < 5; i++) {
for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
int t = (__builtin_ffs(j) - 1) | (i << 5);
if (!vis[t]) {
dfs0(t);
}
}
}
que.push_back(w);
}
inline int dfs1(int w) {
vis.flip(w);
int ret = 1;
for (int i = 0; i < 5; i++) {
for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
int t = (__builtin_ffs(j) - 1) | (i << 5);
if (!vis[t]) {
ret += dfs1(t);
}
}
}
return ret;
}
}scc;

int main() {
freopen("friend.in", "r", stdin);
freopen("friend.out", "w", stdout);
for (int i = 1; i <= m; i++) {
AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
}
for (int i = 1; i <= q; i++) {
qy[i].blk = qy[i].l / BlockSize;
qy[i].id = i;
}
sort(qy + 1, qy + 1 + q);
Bitset CurG[N], CurRG[N];
for (int i = 1, L = 1, R = 0; i <= q; i++) {
if (qy[i].blk != qy[i - 1].blk || i == 1) {
L = qy[i].blk + 1;
R = L - 1;
for (int j = 1; j <= n; j++) {
CurG[j].reset();
CurRG[j].reset();
}
}
if (qy[i].r / BlockSize - 1 > R) {
for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
for (int k = 1; k <= n; k++) {
for (int h = 0; h < 5; h++) {
CurG[k].v[h] ^= PreG[j][k].v[h];
CurRG[k].v[h] ^= PreRG[j][k].v[h];
}
}
}
R = qy[i].r / BlockSize - 1;
}
if (L <= R) {
for (int i = 1; i <= n; i++) {
g[i] = CurG[i];
rg[i] = CurRG[i];
}
for (int l = qy[i].l; l < L * BlockSize; l++) {
}
for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
}
ans[qy[i].id] = scc.solve();
} else {
for (int i = 1; i <= n; i++) {
g[i].reset();
rg[i].reset();
}
for (int j = qy[i].l; j <= qy[i].r; ++j) {
}
ans[qy[i].id] = scc.solve();
}
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}


## 【日常小测】题目2

std的话非常套路啊！

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;

LL vout[N],cnt[N],ans;
int n,m,tot,BLK,pri[N],arr[N],phi[N];
vector<int> divs[N]; bool vis[N];
struct Query{int l,r,id,blk;}q[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Modify(int w, int t) {
for (int j=divs[w].size()-1,c;~j;j--) {
c = divs[w][j];
if (~t) ans += cnt, cnt += phi;
else cnt -= phi, ans -= cnt;
}
}

int main() {
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
n = read(); BLK = sqrt(n) + 1; phi[1] = 1;
for (int i=2;i<=n;i++) {
if (!vis[i]) phi[i] = i-1, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j]) phi[i*pri[j]] = phi[i] * phi[pri[j]];
else {phi[i*pri[j]] = phi[i] * pri[j]; break;}
}
}
for (int i=1;i<=n;i++) {
for (int j=i;j<=n;j+=i)
divs[j].push_back(i);
for (int i=1;i<=m;i++) {
q[i].id = i; q[i].blk = q[i].l / BLK;
}
sort(q+1, q+1+m, [](const Query &A, const Query &B){return A.blk<B.blk||(A.blk==B.blk&&A.r<B.r);});
for (int i=1,l=1,r=0;i<=m;i++) {
while (r > q[i].r) Modify(arr[r--], -1);
while (r < q[i].r) Modify(arr[++r], 1);
while (l > q[i].l) Modify(arr[--l], 1);
while (l < q[i].l) Modify(arr[l++], -1);
vout[q[i].id] = ans;
}
for (int i=1;i<=m;i++) printf("%lld\n",vout[i]);
return 0;
}


## 【BZOJ 4262】Sum

### 题解

ps：矩阵乘法并没有交换律，只有结合律，所以在修改时也得下传标记

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int M = N << 1;
const int MOD = 1000000000;
const int SEED1 = 1023;
const int SEED2 = 1025;

int n,m,tot,arr[N],stk[N];
LL vout[N];
struct Query{
int lim,l,r,t,id;
inline bool operator < (const Query &B) const {
return lim < B.lim;
}
}q[M];

namespace Segment_Tree{
#define SEG Segment_Tree
int ch[M][2],L,R,cnt,root;
LL sum[M],val[M],ans_tmp;
struct Tag{
LL a,b,c,d;
inline Tag() {a=1;b=c=d=0;}
inline Tag(LL a, LL b, LL c, LL d):a(a),b(b),c(c),d(d) {}
inline Tag operator * (const Tag &B) {
return (Tag){a*B.a, B.b+b*B.a, a*B.c+c, B.d+d+b*B.c};
}
}tag[M],delta;

void Build(int &w, int l, int r) {
w = ++cnt;
tag[w] = Tag(1,0,0,0);
val[w] = sum[w] = 0;
if (l < r) {
int mid = l + r + 1 >> 1;
Build(ch[w][0],l,mid-1);
Build(ch[w][1],mid,r);
}
}

inline void init() {
cnt = 0;
Build(root,1,n);
}

inline void Add(int w, int l, int r, Tag v) {
static int len; len = r - l + 1;
sum[w] += val[w] * v.c + len * v.d;
val[w] = val[w] * v.a + len * v.b;
tag[w] = tag[w] * v;
}

inline void push_down(int w, int l, int mid, int r) {
tag[w] = Tag(1,0,0,0);
}

inline void GetSum() {
}

void Modify(int w, int l, int r) {
if (L <= l && r <= R) {
} else {
int mid = l + r + 1 >> 1;
if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d)
push_down(w,l,mid,r);
if (L < mid) Modify(ch[w][0], l, mid-1);
if (R >= mid) Modify(ch[w][1], mid, r);
val[w] = val[ch[w][0]] + val[ch[w][1]];
sum[w] = sum[ch[w][0]] + sum[ch[w][1]];
}
}

inline void modify(int l, int r, int v) {
delta = Tag(0,v,0,0);
L = l, R = r;
Modify(root,1,n);
}

void query(int w, int l, int r) {
if (L <= l && r <= R) {
ans_tmp += sum[w];
} else {
int mid = l + r + 1 >> 1;
if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d)
push_down(w,l,mid,r);
if (L < mid) query(ch[w][0], l, mid-1);
if (R >= mid) query(ch[w][1], mid, r);
}
}

inline LL query(int l, int r) {
ans_tmp = 0;
L = l; R = r;
query(root,1,n);
return ans_tmp;
}
};

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
for (int i=1,l1,l2,r1,r2;i<=m;i++) {
if (l2 > 1) q[++tot] = (Query){l2-1,l1,r1,-1,i};
q[++tot] = (Query){r2,l1,r1,1,i};
n = max(n, max(r1, r2));
}
sort(q+1, q+1+tot);
for (int i=1,c1=SEED1,c2=SEED2;i<=n;i++) {
arr[i] = c1 ^ c2;
c1 = (LL)SEED1 * c1 % MOD;
c2 = (LL)SEED2 * c2 % MOD;
}

SEG::init();
for (int i=1,top=0,cur=1;i<=n;i++) {
while (top && arr[stk[top]] > arr[i]) top--;
SEG::modify(stk[top]+1, i, arr[i]);
SEG::GetSum(); stk[++top] = i;
while (cur <= tot && q[cur].lim == i) {
vout[q[cur].id] -= SEG::query(q[cur].l, q[cur].r) * q[cur].t;
cur++;
}
}
SEG::init();
for (int i=1,top=0,cur=1;i<=n;i++) {
while (top && arr[stk[top]] < arr[i]) top--;
SEG::modify(stk[top]+1, i, arr[i]);
SEG::GetSum(); stk[++top] = i;
while (cur <= tot && q[cur].lim == i) {
vout[q[cur].id] += SEG::query(q[cur].l, q[cur].r) * q[cur].t;
cur++;
}
}

for (int i=1;i<=m;i++)
printf("%lld\n",vout[i]);
return 0;
}


## 【BZOJ 4540】[HNOI2016] 序列

### Code （莫队version）

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const int INF = 2e9;

struct Query{
int l,r,blk,num;
inline bool operator < (const Query &B) const {
return blk < B.blk || (blk == B.blk && r < B.r);
}
}q[N];
int n,m,sqr,top,val[N],stk[N],pos[N],lft[N],rit[N];
LL vout[N],sum_right[N],sum_left[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

namespace Sparse_Table{
#define ST Sparse_Table
int sur[N*3][20],arr[N*3][20],POW[20],log[N];

inline void init() {
POW[0] = 1;
for (int i=1;i<=17;i++)
POW[i] = POW[i-1] << 1;
for (int i=1,w=1;i<=n;w=1,++i)
while (w * 2 <= i) w <<= 1, log[i]++;

for (int i=1;i<=n;i++) {
arr[i][0] = val[i];
sur[i][0] = i;
}
for (int j=1,cur=1;j<=17;j++,cur<<=1) {
for (int i=1;i<=n;i++) {
if (arr[i][j-1] < arr[i+cur][j-1]) {
arr[i][j] = arr[i][j-1];
sur[i][j] = sur[i][j-1];
} else {
arr[i][j] = arr[i+cur][j-1];
sur[i][j] = sur[i+cur][j-1];
}
}
}
}

inline int query(int l, int r) {
int w = log[r-l+1];
if (arr[l][w] < arr[r-POW[w]+1][w]) return sur[l][w];
else return sur[r-POW[w]+1][w];
}
};

inline LL move_right(int l, int r) {
int p = ST::query(l, r);
return sum_left[r] - sum_left[p] + (LL)val[p] * (p - l + 1);
}

inline LL move_left(int l, int r) {
int p = ST::query(l, r);
return sum_right[l] - sum_right[p] + (LL)val[p] * (r - p + 1);
}

inline void prework() {
stk[top = 0] = -INF;
for (int i=1;i<=n;i++) {
while (stk[top] > val[i]) top--;
lft[i] = pos[top];
sum_left[i] = sum_left[pos[top]] + (LL)(i-pos[top]) * val[i];
stk[++top] = val[i];
pos[top] = i;
}

pos[top = 0] = n+1;
for (int i=n;i;i--) {
while (stk[top] >= val[i]) top--;
rit[i] = pos[top];
sum_right[i] = sum_right[pos[top]] + (LL)(pos[top]-i) * val[i];
stk[++top] = val[i];
pos[top] = i;
}

ST::init();
}

int main(){
sqr = sqrt(n);
for (int i=1;i<=n;i++)
prework();
for (int i=1;i<=m;i++) {
q[i].num = i;
q[i].blk = q[i].l / sqr;
}
sort(q+1, q+1+m);

LL cur = val[1];
for (int k=1,l=1,r=1;k<=m;k++) {
while (r < q[k].r) cur += move_right(l,r+1), r++;
while (r > q[k].r) cur -= move_right(l,r), r--;
while (l < q[k].l) cur -= move_left(l,r), l++;
while (l > q[k].l) cur += move_left(l-1,r), l--;
vout[q[k].num] = cur;
}

for (int i=1;i<=m;i++)
printf("%lld\n",vout[i]);
return 0;
}


ps：这一份代码并不能处理值为负数的情况，至于为什么：我也普吉岛 QwQ

—————————— UPD 2017.2.2 ——————————

1. $l_i$,$r_i$都没有被询问限制
2. 有一个被限制
3. 有两个被限制

## 【BZOJ 3585】mex

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int arr[N],cnt[N],n,m,block,vout[N];
set<int> ans;
struct Query{
int l,r,b,id;
bool operator < (const Query & B) const {
return b < B.b || (b == B.b && r < B.r);
}
}q[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void update(int ty, bool delta) {
if (ty > n) return;
if (delta) {
cnt[ty]++;
if (cnt[ty] == 1) {
ans.erase(ty);
}
} else {
cnt[ty]--;
if (!cnt[ty]) {
ans.insert(ty);
}
}
}

int main(){
for (int i=1;i<=n;i++) {
ans.insert(i);
} ans.insert(0);
for (int i=1;i<=m;i++) {
q[i].b = q[i].l / block;
q[i].id = i;
}
sort(q+1, q+1+m);

for (int i=1,p1=1,p2=0,l,r;i<=m;i++) {
l = q[i].l; r = q[i].r;
while (p1 < l) update(arr[p1++], 0);
while (p2 > r) update(arr[p2--], 0);
while (p2 < r) update(arr[++p2], 1);
while (p1 > l) update(arr[--p1], 1);
vout[q[i].id] = *(ans.begin());
}

for (int i=1;i<=m;i++) {
printf("%d\n",vout[i]);
}
return 0;
}