12月下半月做题记 - cool's Blog
12月下半月做题记
已经意识模糊，完全鏼不动题了，看看这几天能鏼几道比较好的题。
[CF581F]一颗无根树，对点黑白染色，要求所有叶子节点染黑的和染白的数量一样，求最少有多少条树边连接两个异色点。
首先如果点数大于2肯定能找到一个不是叶节点的根，然后以他为根。
dp[i][j][0]为i这棵子树染j个叶子i染白色的最少答案。
显然可以O（n^2）转移。但这样好像爆空间了，因为dp[i][j][0] = dp[i][S-j][1]
就可以省掉一维。
#include <cstdio>
#include <cstring>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 5010
template<class T>T min(T a,T b){ return a<b?a:b;}
int dp[N][N],f[N],last[N<<1],h[N<<1],head[N],l,n,T,rt,x,y;
void add(int x,int y)
{
h[++l] = y;
last[l] = head[x];
head[x] = l;
}
int dfs(int x,int fa)
{
int p = (!last[head[x]]);
dp[x][0] = 0;
for (int i = head[x],y,z;i;i = last[i])
{
if ((y=h[i]) == fa) continue;
z = dfs(y,x);
memset(f,63,sizeof(f));
rep(j,0,p)
{
rep(k,0,z) f[j+k] = min(f[j+k],dp[x][j]+dp[y][k]);
rep(k,0,z) f[j+k] = min(f[j+k],dp[x][j]+dp[y][z-k]+1);
}
p += z;
memcpy(dp[x],f,sizeof(f));
}
return p;
}
int main()
{
scanf("%d",&n);
rep(i,2,n)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
memset(dp,63,sizeof(dp));
if (n == 2){ puts("1"); return 0; }
for (rt = 1;!last[head[rt]];rt++);
T = dfs(rt,0);
printf("%d",dp[rt][T/2]);
return 0;
}
[51nod1685]定义一个长度为奇数的区间的权值为其中位数，求K大的奇数区间。
二分答案。sum[i]为前缀中>=mid的数量。
若区间[L,R]的中位数>=mid,则(a[R]-a[L-1])*2>R-L+1
a[R]*2-R>a[L-1]*2-(L-1)
也就是统计有多少对L,R满足 0<=L<R<=n，且a[L]*2-L<a[R]*2-R且L,R奇偶性不同。
维护奇偶的树状数组即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 800010
#define maxn 800000
using namespace std;
int g[2][N],gg[N],a[N],n,k,L,R,tot,ans,sum[N];
void add(int g[],int x,int y)
{
for (;x <= maxn;x += x&-x)
g[x] += y;
}
int query(int g[],int x)
{
int y = 0;
for (;x;x -= x&-x)
y += g[x];
return y;
}
int main()
{
scanf("%d%d",&n,&k);
rep(i,1,n) scanf("%d",&a[i]),gg[i] = a[i];
sort(gg+1,gg+n+1);
rep(i,1,n) a[i] = lower_bound(gg+1,gg+n+1,a[i])-gg;
for (L=1,R=n;L<=R;)
{
int mid = L+R>>1;
tot = 0; memset(g,0,sizeof(g));
add(g[0],2*n,1);
rep(i,1,n)
{
sum[i] = sum[i-1]+(a[i]>=mid);
tot += query(g[(i&1)^1],2*n+2*sum[i]-i-1);
add(g[i&1],2*n+2*sum[i]-i,1);
}
if (tot >= k) ans = mid,L = mid+1;
else R = mid-1;
}
printf("%d",gg[ans]);
return 0;
}
[****]求区间lcm，n<=1e5 a[i]<=1e9
思路很神。
考虑将一个数分解，如果一个数有一个质数p出现了k次，那么加入k个数分别为p,p^2,……,p^k，每个数权值为p。
那么就相当于求区间内不同数的权值积（注意区分数和权值）
#include <cstdio>
#include <map>
#include <algorithm>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 100010
#define E 100000
#define M 3000010
#define zhl 1000000007
#define ll long long
using namespace std;
map<int,int>mp;
struct xfy
{
int id,num,val;
}a[M];
struct hcy
{
int l,r,id;
}ask[N];
int vis[N],pri[N],len;
void init()
{
rep(i,2,E)
{
if (!vis[i]) pri[++len] = i;
for (int j = 1;j <= len&&pri[j]*i <= E;j++)
{
vis[pri[j]*i] = 1;
if (i % pri[j] == 0) break;
}
}
}
int tot,cnt;
void fj(int x,int id)
{
rep(i,1,len)
{
if (pri[i]*pri[i] > x) break;
for (int t = 1;x % pri[i] == 0;x /= pri[i])
{
t *= pri[i];
if (!mp[t]) mp[t] = ++cnt;
a[++tot] = (xfy){id,mp[t],pri[i]};
}
}
if (x != 1)
{
if (!mp[x]) mp[x] = ++cnt;
a[++tot] = (xfy){id,mp[x],x};
}
}
int n,q,x,lan[M],tmp;
ll g[N],ans[N];
void add(int x,int y)
{
for (;x <= n;x += x&-x)
g[x] = g[x]*y%zhl;
}
ll query(int x)
{
ll y = 1;
for (;x;x -= x&-x)
y = y*g[x]%zhl;
return y;
}
ll pow(ll x,ll y)
{
ll ans = 1;
for (;y;x = x*x%zhl,y >>= 1)
if (y&1) ans = ans*x%zhl;
return ans;
}
ll ni(ll x)
{
return pow(x,zhl-2);
}
int cmp(hcy x,hcy y)
{
return x.r < y.r;
}
int main()
{
scanf("%d%d",&n,&q);
init();
rep(i,1,n) scanf("%d",&x),fj(x,i);
rep(i,1,q) scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].id = i;
sort(ask+1,ask+q+1,cmp);
int j = 1,k = 1;
rep(i,0,n) g[i] = 1;
rep(i,1,n)
{
for (;j <= tot && a[j].id == i;j++)
{
add(i,a[j].val);
if (tmp = lan[a[j].num]) add(a[tmp].id,ni(a[tmp].val));
lan[a[j].num] = j;
}
for (;k <= q && ask[k].r == i;k++)
ans[ask[k].id] = query(ask[k].r)*ni(query(ask[k].l-1))%zhl;
}
rep(i,1,q) printf("%lld\n",ans[i]);
return 0;
}
[51nod1471]每次将一段区间的末尾插入到开头，每次求一段区间内有多少数等于k。
块状链表维护，O（n^1.5）
人生第一次写（chao）块状链表，觉得这个实现方法好神。
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define N 100010
#define E 330
using namespace std;
int n,q,cnt,a[N],l[E],r[E],blk,tmp[E],S,pos[N],x,y,ty,lastans,k,bx,by;
struct zhl
{
int b[E],s[N],head,tot;
void build(int l,int r)
{
rep(i,l,r) s[b[tot++] = a[i]]++;
}
void right(int st)
{
if ((--head) < 0) head += tot;
cnt = b[head];
s[cnt]--; s[st]++;
b[head] = st;
}
void reset()
{
if(head == 0) return;
rep(i,0,tot-1) tmp[i] = b[i];
int u = 0;
rep(i,head,tot-1) b[u++] = tmp[i];
rep(i,0,head-1) b[u++] = tmp[i];
head = 0;
}
void update(int st,int l,int r)
{
reset();
cnt = b[r]; s[cnt]--;
drep(i,r,l+1) b[i] = b[i-1];
b[l] = st; s[st]++;
}
int get(int k)
{
k = head + k;
if (k >= tot) k -= tot;
return b[k];
}
int cal(int l,int r,int k)
{
reset();
int res = 0;
rep(i,l,r) if(b[i] == k) res++;
return res;
}
}b[E];
int main()
{
scanf("%d",&n); blk = sqrt(n);
rep(i,1,n) scanf("%d",&a[i]), pos[i] = (i-1)/blk+1;
for (int i = 1;i <= n;i += blk)
{
l[pos[i]] = i;
r[pos[i]] = i+blk-1;
}
r[S=pos[n]] = n;
rep(i,1,S) b[i].build(l[i],r[i]);
for (scanf("%d",&q);q--;)
{
scanf("%d%d%d",&ty,&x,&y);
x = (x+lastans-1)%n+1;
y = (y+lastans-1)%n+1;
if (x > y) k = x,x = y,y = k;
bx = pos[x]; by = pos[y];
if (ty>1)
{
scanf("%d",&k);
k = (k+lastans-1)%n+1;
lastans = 0;
if (bx^by)
{
lastans += b[bx].cal(x-l[bx],r[bx]-l[bx],k);
lastans += b[by].cal(0,y-l[by],k);
rep(i,bx+1,by-1) lastans += b[i].s[k];
}
else lastans = b[bx].cal(x-l[bx],y-l[bx],k);
printf("%d\n",lastans);
}
else
{
cnt = b[by].get(y-l[by]);
if (bx^by)
{
b[bx].update(cnt,x-l[bx],r[bx]-l[bx]);
rep(i,bx+1,by-1) b[i].right(cnt);
b[by].update(cnt,0,y-l[by]);
}
else b[bx].update(cnt,x-l[bx],y-l[bx]);
}
}
return 0;
}
[bzoj3878]有n个操作，每个操作有4种类型：
1.+A 2.-A 3.*A 4.+A*X （X为一次操作都没做时的值）
有Q个数，每个数都按顺序经过这n个操作，操作过程中如果某个值大于R，就变为R，如果小于L就变为L。
求Q个数的答案。
离线处理。因为如果a<b，那么最后算出来的结果a'是不可能大于b'的。
所以从小到大排序后，每次对整个区间进行一次操作，线段树计算某个区间如果这个区间的最小值>R则全体变R，如果最大值<L则全体变L，如果这个区间的最小值和最大值都>L,<R，那这个区间就可以先打标记。
大概就是在线段树上二分。这样好像是O（nlog^2）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a);
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
#define M (1<<18)+10
char s1[10];
int p[N],n,q;
ll s[N],Left,Right,h[N],gg[N];
struct tag
{
ll a,b,c;
tag(){a = 1,b = c = 0;}
tag(ll x,ll y,ll z):a(x),b(y),c(z){};
inline void operator += (tag o)
{
a *= o.a; b = b*o.a+o.b; c = c*o.a+o.c;
}
inline ll cal(const ll& x)
{
return min(max(Left,x*(a+b)+c),Right);
}
}L[M],R[M],lazy[M];
inline void pushdown(const int& k)
{
tag v = lazy[k];
lazy[k<<1] += v; L[k<<1] += v; R[k<<1] += v;
lazy[k<<1|1] += v; L[k<<1|1] += v; R[k<<1|1] += v;
lazy[k] = tag(1,0,0);
}
inline void pushup(const int& k)
{
L[k] = L[k<<1]; R[k] = R[k<<1|1];
}
void solve(int k,int l,int r)
{
if (l > r) return;
if (R[k].cal(h[r]) != Right && L[k].cal(h[l]) != Left) return;
if (l < r) pushdown(k);
if (L[k].cal(h[l]) == Right) { lazy[k] = L[k] = R[k] = tag(0,0,Right); return;}
if (R[k].cal(h[r]) == Left) { lazy[k] = L[k] = R[k] = tag(0,0,Left); return;}
int mid = l+r>>1;
solve(k<<1,l,mid); solve(k<<1|1,mid+1,r);
pushup(k);
}
void calevery(int k,int l,int r)
{
if (l == r) { h[l] = L[k].cal(h[l]); return; }
pushdown(k);
int mid = l+r>>1;
calevery(k<<1,l,mid);
calevery(k<<1|1,mid+1,r);
}
int main()
{
scanf("%d%lld%lld",&n,&Left,&Right);
rep(i,1,n)
{
scanf("%s%lld",s1,&s[i]);
if (s1[0] == '+') p[i] = 1;
else if (s1[0] == '-') p[i] = 2;
else if (s1[0] == '*') p[i] = 3;
else p[i] = 4;
}
scanf("%d",&q);
rep(i,1,q) scanf("%lld",&h[i]),gg[i] = h[i];
sort(h+1,h+q+1);
rep(i,1,q) gg[i] = lower_bound(h+1,h+q+1,gg[i])-h;
rep(i,1,n)
{
tag v;
if (p[i] == 1) v = tag(1,0,s[i]);
else if (p[i] == 2) v = tag(1,0,-s[i]);
else if (p[i] == 3) v = tag(s[i],0,0);
else v = tag(1,s[i],0);
lazy[1] += v; L[1] += v; R[1] += v;
solve(1,1,q);
}
calevery(1,1,q);
rep(i,1,q) printf("%lld\n",h[gg[i]]);
return 0;
}
[bzoj3622] 给定两个长度为n个序列，保证这2n个数字两两不同，求有多少匹配满足a[i]>b[i]的数对数比a[i]<b[i]的数对数多k。
好神的题目，这个方程我是怎么也想不出了TAT
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000009
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 2010
ll f[N][N],g[N],fac[N],C[N][N];
int a[N],b[N],n,k,fst[N];
int main()
{
scanf("%d%d",&n,&k);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n) scanf("%d",&b[i]);
if ((n+k)&1) return puts("0"),0;
k = (n+k)>>1;
sort(a+1,a+n+1); sort(b+1,b+n+1);
int j = 1;
rep(i,1,n)
{
for (;j <= n && a[j] < b[i];j++);
fst[i] = j;
}
rep(i,1,n+1) f[i][0] = 1;
drep(i,n,1) drep(j,n-i+1,1)
{
f[i][j] = f[i+1][j]+f[i+1][j-1]*max(0,n-fst[i]+1-j+1)%zhl;
if (f[i][j] >= zhl) f[i][j] -= zhl;
}
fac[1] = 1;
rep(i,2,n) fac[i] = fac[i-1]*i%zhl;
rep(i,0,n)
{
C[i][0]=C[i][i]=1;
rep(j,1,i-1)
{
C[i][j]=C[i-1][j-1]+C[i-1][j];
if (C[i][j] >= zhl) C[i][j] -= zhl;
}
}
drep(i,n,0)
{
g[i] = f[1][i]*fac[n-i]%zhl;
rep(j,i+1,n)
{
g[i] -= g[j]*C[j][i]%zhl;
if (g[i] < 0) g[i] += zhl;
}
}
printf("%lld",g[k]);
return 0;
}
[bzoj4596]有若干条边，每条边有一个标号（1~n-1），求一棵不含重复标号的生成树数量（n<=17）。
首先生成树数量就想到矩阵树定理，考虑容斥。
对于每个点集的边都做一次矩阵树，然后根据点数和n的奇偶性搞一下即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 20
int n,s[N],a[N][N*N],b[N][N*N],all,cnt,x;
ll res,A[N][N],ans;
void add(ll& x,ll y)
{
x += y;
if (x >= zhl) x -= zhl;
if (x < 0) x += zhl;
}
int get(int S)
{
clr(A,0);
int x = 0,ss = 1,u,v;
rep(i,1,n)
{
if (S&ss)
{
x++;
drep(j,s[i],1)
{
u = a[i][j], v = b[i][j];
A[u][v]--; A[v][u]--;
A[u][u]++; A[v][v]++;
}
}
ss = ss+ss;
}
return x;
}
ll gauss()
{
ll ans = 1;
int f = 1;
rep(i,1,n)
{
rep(j,i+1,n) for (;A[j][i];f = -f)
{
ll t = A[i][i]/A[j][i];
rep(k,i,n) add(A[i][k],-A[j][k]*t%zhl);
rep(k,i,n) swap(A[i][k],A[j][k]);
}
if (A[i][i] == 0) return 0;
ans = ans*A[i][i]%zhl;
}
return f>0?ans:zhl-ans;
}
int main()
{
scanf("%d",&n); n--;
rep(i,1,n)
{
scanf("%d",&x);
rep(j,1,x) scanf("%d%d",&a[i][j],&b[i][j]);
s[i] = x;
}
all = (1<<n)-1;
rep(S,1,all)
{
cnt = get(S);
res = gauss();
if ((n-cnt)&1) add(ans,-res);
else add(ans,res);
}
printf("%lld",ans);
return 0;
}
2016.12.26 19:52
终于200题了（仰望500+畜牧）
[bzoj1810]给出n*m的矩阵，求两个不相交的矩阵使这两个矩阵内部的权值和都恰好为k，且周长和最小。
两个不相交的矩阵说明肯定可以找到一条竖线或一条横线把两个矩形分开。
统计每条竖线和横线左右上下最小的即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 255
int a[N][N],L,W,n,k,x,y,x1,x2,now,P,ans,f[4][N];
void checkmin(int& x,int y)
{
if (x > y) x = y;
}
int getsum(int x,int y,int z,int w)
{
return a[z][w]-a[x-1][w]-a[z][y-1]+a[x-1][y-1];
}
int getp(int x,int y,int z,int w)
{
return ((z-x+1)+(w-y+1))*2;
}
int main()
{
scanf("%d%d%d%d",&L,&W,&n,&k);
rep(i,1,n)
{
scanf("%d%d",&x,&y);
a[x][y]++;
}
rep(i,1,L) rep(j,1,W) a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
/* rep(i,1,L)
{
rep(j,1,W) printf("%d ",a[i][j]);
puts("");
}*/
clr(f,63);
rep(i,1,W) rep(j,i,W)
{
x1 = x2 = 1;
for (;x2 <= L;x2++)
{
for (;x1<x2 && getsum(x1,i,x2,j)>k;x1++);
now = getsum(x1,i,x2,j);
//printf("%d %d %d %d %d\n",x1,i,x2,j,now);
for (;getsum(x1,i,x2,j) == k;x1++)
{
// printf("%d %d %d %d %d\n",x1,i,x2,j,now);
P = getp(x1,i,x2,j);
checkmin(f[0][i],P);
checkmin(f[1][j],P);
checkmin(f[2][x1],P);
checkmin(f[3][x2],P);
if (x1 == x2) break;
}
}
}
rep(i,1,L) checkmin(f[3][i],f[3][i-1]);
drep(i,L,1) checkmin(f[2][i],f[2][i+1]);
rep(i,1,W) checkmin(f[1][i],f[1][i-1]);
drep(i,W,1) checkmin(f[0][i],f[0][i+1]);
ans = inf;
rep(i,1,L) checkmin(ans,f[2][i]+f[3][i-1]);
rep(i,1,W) checkmin(ans,f[0][i]+f[1][i-1]);
if (ans < inf) printf("%d",ans);
else puts("NO");
return 0;
}
[bzoj1813]给出n个1~n的数，min(max(min(n-(a[i]-k)%n,(a[i]-k)%n)))
等价于求1~n的循环序列中最长的没有出现连续数的个数C。最后答案为（n-C）/2
比如2,2,2,3,5,5 最长的没出现的是6,1 所以答案是2。
为什么这样是对的？因为(n-C)其实就是5-2+1，也就是说k肯定是某两个数的平均数。（说的不是很清楚，自行理解下）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 1000010
int a[N],b[N],mx,cnt,ans,n;
int main()
{
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n)
{
int x = a[i]-i;
if (x <= 0) x += n;
b[x] = 1;
}
rep(i,1,n) if (!b[i]) cnt++;
else mx = max(mx,cnt),cnt = 0;
rep(i,1,n) if (!b[i]) cnt++;
else {mx = max(mx,cnt),cnt = 0; break;}
ans = mx;
clr(b,0);
rep(i,1,n)
{
int x = a[i]+i;
if (x > n) x -= n;
b[x] = 1;
}
mx = cnt = 0;
rep(i,1,n) if (!b[i]) cnt++;
else mx = max(mx,cnt),cnt = 0;
rep(i,1,n) if (!b[i]) cnt++;
else {mx = max(mx,cnt),cnt = 0; break;}
ans = max(ans,mx);
printf("%d",(n-ans)/2);
return 0;
}
[bzoj4237]给出平面内横纵坐标都不相同的n个点，选出两个点作为一个矩形的左下角和右上角，求有多少个矩形内部没有点。
首先考虑一个右上角，左下角肯定是一个凸包，但是这个凸包并不是随着x增大单调的，所以考虑分治。
每次选出y<=mid和y>mid的点，这样的话凸包肯定是单调的（因为不会有点的y小于凸包中的点）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 200010
struct xfy
{
int x,y;
xfy(){}
xfy(int _x,int _y):x(_x),y(_y){}
}p[N],t[N],st1[N],st2[N];
int n,gg[N],x,y;
ll ans;
bool cmpx(xfy x,xfy y)
{
return x.x < y.x;
}
void solve(int l,int r)
{
if (l == r) return;
int mid = l+r>>1,len1 = l-1,len2 = mid;
rep(i,l,r) if (p[i].y <= mid)
t[++len1] = p[i];
else t[++len2] = p[i];
memcpy(p+l,t+l,sizeof(xfy)*(r-l+1));
int top1 = 0, top2 = 0, j = l;
rep(i,mid+1,r)
{
for (;j <= mid && p[j].x < p[i].x;j++)
{
for (;top2&&st2[top2].y < p[j].y;top2--);
st2[++top2] = p[j];
}
for (;top1&&st1[top1].y > p[i].y;top1--);
st1[++top1] = p[i];
int x = upper_bound(st2+1,st2+top2+1,st1[top1-1],cmpx)-st2;
ans += top2-x+1;
}
solve(l,mid); solve(mid+1,r);
}
int main()
{
scanf("%d",&n);
rep(i,1,n)
{
scanf("%d%d",&x,&y);
gg[i] = x;
p[i] = xfy(x,y);
}
sort(gg+1,gg+n+1);
rep(i,1,n) p[i].x = lower_bound(gg+1,gg+n+1,p[i].x)-gg;
rep(i,1,n) gg[i] = p[i].y;
sort(gg+1,gg+n+1);
rep(i,1,n) p[i].y = lower_bound(gg+1,gg+n+1,p[i].y)-gg;
sort(p+1,p+n+1,cmpx);
solve(1,n);
printf("%lld",ans);
return 0;
}
[bzoj4154]每次将一个点的子树中深度小于k的点染成c，求某个点的颜色。
将一个点转化一个二维点，横坐标为其dfs序，纵坐标为深度，那么修改就是对(st[i],dep[i],ed[i],k)这个矩阵进行修改。
用KD树+lazy维护即可。（为什么我跑的这么慢）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
int st[N],ed[N],dep[N],cnt,lazy[N],id[N],_,n,D,c,Q,x,y,z,rt;
int h[N],last[N],head[N],l;
ll ans;
struct xfy
{
int mx[2],mi[2],d[2];
int l,r,f,col;
void input(int i)
{
l = r = 0;
f = i; col = 1;
mx[0] = mi[0] = d[0] = st[i];
mx[1] = mi[1] = d[1] = dep[i];
}
int& operator [](int x)
{
return d[x];
}
}T[N];
void add(int x,int y)
{
h[++l] = y;
last[l] = head[x];
head[x] = l;
}
void dfs(int x)
{
st[x] = ++cnt;
for (int i = head[x],y;i;i = last[i])
dep[y = h[i]] = dep[x]+1, dfs(y);
ed[x] = cnt;
}
inline bool cmp(xfy x,xfy y)
{
return x[D] < y[D];
}
inline void checkmin(int& x,int y) { if (x > y) x = y; }
inline void checkmax(int& x,int y) { if (x < y) x = y; }
inline void up(int x,int y)
{
rep(i,0,1) checkmin(T[x].mi[i],T[y].mi[i]),checkmax(T[x].mx[i],T[y].mx[i]);
}
inline void pushdown(const int& k)
{
if (lazy[k])
{
int d = lazy[k];
lazy[T[k].l] = lazy[T[k].r] = d;
T[T[k].l].col = T[T[k].r].col = d;
lazy[k] = 0;
}
}
int build(int l,int r,int now,int fa)
{
D = now;
int mid = l+r>>1;
nth_element(T+l,T+mid,T+r,cmp);
id[T[mid].f] = mid;
T[mid].f = fa;
T[mid].mi[0] = T[mid].mx[0] = T[mid][0];
T[mid].mi[1] = T[mid].mx[1] = T[mid][1];
if (l < mid) T[mid].l = build(l,mid-1,now^1,mid),up(mid,T[mid].l);
if (r > mid) T[mid].r = build(mid+1,r,now^1,mid),up(mid,T[mid].r);
return mid;
}
void update(int k,int v,const int& x1,const int& y1,const int& x2,const int& y2)
{
if (T[k].mi[0] > x2 || T[k].mx[0] < x1 || T[k].mi[1] > y2 || T[k].mx[0] < y1) return;
// printf("%d %d\n",k,v);
if (T[k].mi[0] >= x1 && T[k].mx[0] <= x2 && T[k].mi[1] >= y1 && T[k].mx[1] <= y2)
{
lazy[k] = T[k].col = v;
return;
}
pushdown(k);
if (T[k][0] >= x1 && T[k][0] <= x2 && T[k][1] >= y1 && T[k][1] <= y2) T[k].col = v;
if (T[k].l) update(T[k].l,v,x1,y1,x2,y2);
if (T[k].r) update(T[k].r,v,x1,y1,x2,y2);
}
void query(int k)
{
if (T[k].f) query(T[k].f);
pushdown(k);
}
int main()
{
for (scanf("%d",&_);_--;ans = 0)
{
scanf("%d%d%d",&n,&c,&Q);
clr(head,0); l = cnt = 0;
rep(i,2,n) scanf("%d",&x), add(x,i);
dep[1] = 1;
dfs(1);
rep(i,1,n) T[i].input(i);
clr(lazy,0);
rt = build(1,n,0,0);
rep(i,1,Q)
{
scanf("%d%d%d",&x,&y,&z);
if (!z)
{
query(id[x]);
ans = (ans+(ll)i*T[id[x]].col%zhl)%zhl;
}
else update(rt,z,st[x],dep[x],ed[x],dep[x]+y);
}
printf("%lld\n",ans);
}
return 0;
}
2022年8月20日 01:50
Argos doesn't currently offer a student discount, however they offer year round sales both online and in store, argos uk and you can also find great discount vouchers online. Keep an eye on this website for the latest deals we find so you can get yourself a bargain. student discount card and app giving you access to huge offers on food and essentials, tech, travel and home delivery.
2022年8月20日 19:43
Secondary Education Core | Bellevue University 2021. Bellevue teachers vote to pause expansion of in-person learning 2021. bellevue.edu Parents grow frustrated with Bellevue teachers meeting over. Parents grow frustrated with Bellevue teachers meeting over 2021