H Moving Points
题目链接：https://vjudge.net/contest/358745#problem/H
思路：树状数组维护，类似于树状数组求逆序对+思维（思维量很小）
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
typedef long long ll;
struct node{
ll a,b;
friend bool operator <(node a,node b){
return a.a<b.a;
}
}a[N];
ll b[N];
ll h[N];
ll c1[N],c2[N];
int m,n;
void des(){
sort(h+1,h+n+1);m=0;
for(int i=1;i<=n;i++){
if(i==1||h[i]!=h[i-1]){
b[++m]=h[i];
}
}
}
int query(ll x){
return lower_bound(b+1,b+m+1,x)-b;
}
int lowbit(int x){
return x&(-x);
}
void update1(int x,ll v){
for(int i=x;i<=m;i+=lowbit(i)){
c1[i]+=v;
}
// for(int i=1;i<=m;i++)cout<<c1[i]<<" ";puts("");
}
void update2(int x,ll v){
for(int i=x;i<=m;i+=lowbit(i)){
c2[i]+=v;
}
}
ll query1(ll x){
ll ans=0;
for(ll i=x;i;i-=lowbit(i)){
ans+=c1[i];
}
return ans;
}
ll query2(ll x){
ll ans=0;
for(int i=x;i;i-=lowbit(i)){
ans+=c2[i];
}
return ans;
}
int main(){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
while(~scanf("%d",&n)){
m=0;
memset(c1,0,sizeof c1);
memset(c2,0,sizeof c2);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].a);
}
for(int i=1;i<=n;i++){
scanf("%lld",&a[i].b);
h[i]=a[i].b;
}
des();
sort(a+1,a+n+1);
ll ans=0;
// for(int i=1;i<=m;i++){
// cout<<b[i]<<" ";
// }puts("");
for(int i=1;i<=n;i++){
int x=query(a[i].b);
ll y=query1(x),z=query2(x);
// cout<<x<<endl;
ans+=(y*a[i].a-z);
update1(x,1ll);
update2(x,a[i].a);
// cout<<y<<" "<<z<<endl;
}
printf("%lld\n",ans);
}
}
I - Mayor’s posters
题目链接：https://vjudge.net/contest/358745#problem/I
思路：插点离散化+懒惰标记的应用
#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+9;
typedef long long ll;
struct node{
int l,r;
int lazy;
}tree[N<<2];
int n;
void build(int rt,int l,int r){
tree[rt].l=l,tree[rt].r=r;
tree[rt].lazy=0;
if(l==r)return;
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
int L[N],R[N],ans[N];
vector<int>point;
void pushdown(int rt){
if(tree[rt].lazy!=0){
tree[rt<<1|1].lazy=tree[rt<<1].lazy=tree[rt].lazy;
tree[rt].lazy=0;
}
}
void change(int rt,int l,int r,int x){
if(tree[rt].l>=l&&tree[rt].r<=r){
tree[rt].lazy=x;
return;
}
pushdown(rt);
int mid=(tree[rt].l+tree[rt].r)>>1;
if(l<=mid)change(rt<<1,l,r,x);
if(r>mid)change(rt<<1|1,l,r,x);
}
void query(int rt,int l,int r){
if(tree[rt].lazy){
ans[tree[rt].lazy]=1;
return;
}
pushdown(rt);
if(tree[rt].l==tree[rt].r)return;
int mid=(tree[rt].l+tree[rt].r)>>1;
query(rt<<1,l,r);
query(rt<<1|1,l,r);
}
int main(){
int _;
scanf("%d",&_);
while(_--){
scanf("%d",&n);point.clear();
for(int i=1;i<=n;i++){
scanf("%d%d",&L[i],&R[i]);
point.push_back(L[i]);
point.push_back(R[i]);
}
sort(point.begin(),point.end());
point.erase(unique(point.begin(),point.end()),point.end());
int m=point.size();
for(int i=0;i<m-1;i++){
if(point[i+1]-point[i]>1){
point.push_back(point[i+1]-1);
}
}
sort(point.begin(),point.end());
m=point.size();
build(1,0,m-1);memset(ans,0,sizeof ans);
for(int i=1;i<=n;i++){
int x=lower_bound(point.begin(),point.end(),L[i])-point.begin();
int y=lower_bound(point.begin(),point.end(),R[i])-point.begin();
change(1,x,y,i);
}
int res=0;query(1,0,m-1);
for(int i=1;i<=n;i++){
if(ans[i])res++;
}
printf("%d\n",res);
}
}
J - Atlantis
题目链接：https://vjudge.net/contest/358745#problem/J
思路：课上讲过这里不在赘述，不过要注意c++11要用.f
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define debug puts("*");
const int N=220;
int n,cnt,t=1;
struct node{
int l,r,cnt;
double len;
}tree[N<<2];
struct knode{
double x1,y1,y2;
int k;
friend bool operator <(knode a,knode b){
return a.x1<b.x1;
}
}line[N];
double raw[N],b[N],val[N];
void discrete(){
sort(raw+1,raw+2*n+1);
// rep(i,1,2*n)cout<<raw[i]<<" ";puts("");
rep(i,1,2*n)
if(i==1||raw[i]!=raw[i-1])
b[++cnt]=raw[i];
// rep(i,1,cnt)cout<<b[i]<<" ";
}
int findx(double x){
return lower_bound(b+1,b+cnt+1,x)-b;
}
void pushup(int rt,int l,int r){
if(tree[rt].cnt){
tree[rt].len=b[r+1]-b[l];
}
else if(l!=r){
tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
}else tree[rt].len=0;
return ;
}
void build(int rt,int l,int r){
tree[rt].l=l,tree[rt].r=r;
tree[rt].len=0.0;tree[rt].cnt=0;
// cout<<l<<" "<<r<<endl;
if(l==r)return;
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void update(int rt,int l,int r,int x){
if(l<=tree[rt].l&&tree[rt].r<=r){
tree[rt].cnt+=x;
pushup(rt,tree[rt].l,tree[rt].r);
return;
}
int mid=(tree[rt].l+tree[rt].r)>>1; ///2
if(l<=mid)update(rt<<1,l,r,x);
if(r>mid)update(rt<<1|1,l,r,x);
pushup(rt,tree[rt].l,tree[rt].r);
}
int main(){
while(~scanf("%d",&n)){
if(!n)break;
cnt = 0; /// 1
rep(i,1,n){
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
raw[i*2-1]=y1,raw[i*2]=y2;
line[i*2-1].x1=x1,line[i*2-1].y1=y1,line[i*2-1].y2=y2;
line[i*2-1].k=1;
line[i*2].x1=x2,line[i*2].y1=y1,line[i*2].y2=y2;
line[i*2].k=-1;
}
discrete();
sort(line+1,line+2*n+1);
double ans=0;
build(1,1,cnt);
rep(i,1,2*n){
ans+=tree[1].len*(line[i].x1-line[i-1].x1);
update(1,findx(line[i].y1),findx(line[i].y2)-1,line[i].k);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", t++, ans);
}
}
K - A Simple Problem with Integers
思路：课上例题，lazy标记应用
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+9;
struct node{
ll l,r;
ll data,add;
}m[N<<2];
ll a[N];
void pushdown(ll rt,ll len){
if(m[rt].add){
m[rt<<1].add+=m[rt].add;
m[rt<<1|1].add+=m[rt].add;
m[rt<<1].data+=(m[rt].add*((ll)len-(len>>1)));
m[rt<<1|1].data+=(m[rt].add*((ll)len>>1));
m[rt].add=0;
}
}
void build(ll rt,ll l,ll r){
m[rt].l=l;
m[rt].r=r;
m[rt].add=0;
if(l==r){
m[rt].data=a[l];
return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
m[rt].data=m[rt<<1].data+m[rt<<1|1].data;
}
void update(ll l,ll r,ll v,ll rt){
if(l<=m[rt].l&&r>=m[rt].r){
m[rt].add+=v;
m[rt].data+=(v*(m[rt].r-m[rt].l+1ll));
return;
}
pushdown(rt,m[rt].r-m[rt].l+1);
int mid=(m[rt].r+m[rt].l)>>1;
if(mid>=l)update(l,r,v,rt<<1);
if(mid<r)update(l,r,v,rt<<1|1);
m[rt].data=m[rt<<1|1].data+m[rt<<1].data;
}
ll query(ll l,ll r,ll p){
if(m[p].l>=l&&m[p].r<=r){
return m[p].data;
}
int mid=(m[p].l+m[p].r)>>1;
pushdown(p,m[p].r-m[p].l+1);
ll ans=0;
if(mid>=l)ans+=query(l,r,p<<1);
if(mid<r)ans+=query(l,r,p<<1|1);
return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);
while(m--){
char c[4];
scanf("%s",c);
ll x,y;ll z;
if(c[0]=='Q'){
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(x,y,1));
}
else{
scanf("%lld%lld%lld",&x,&y,&z);
update(x,y,z,1);
}
}
}
L - Black And White
思路：区间合并的典型例题，最好自己写一遍，我写的时候出了太多bug，这个代码还是借用的。。。
这里更新一下，贴上我自己的代码，原来是懒惰标记忘记清空了，实在是太菜了
#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
const int N=1e5+9;
int a[N],n,m;
int tree0[N<<2],tree1[N<<2],lazy[N<<2],lmax0[N<<2];
int lmax1[N<<2],rmax0[N<<2],rmax1[N<<2];
void swp(int rt){
swap(tree0[rt],tree1[rt]);
swap(rmax0[rt],rmax1[rt]);
swap(lmax0[rt],lmax1[rt]);
return;
}
void pushup(int rt){
if(!tree0[lson])lmax1[rt]=lmax1[lson]+lmax1[rson];
else lmax1[rt]=lmax1[lson];
if(!tree1[lson])lmax0[rt]=lmax0[lson]+lmax0[rson];
else lmax0[rt]=lmax0[lson];
if(!tree0[rson])rmax1[rt]=rmax1[rson]+rmax1[lson];
else rmax1[rt]=rmax1[rson];
if(!tree1[rson])rmax0[rt]=rmax0[rson]+rmax0[lson];
else rmax0[rt]=rmax0[rson];
tree0[rt]=max(rmax0[lson]+lmax0[rson],max(tree0[lson],tree0[rson]));
tree0[rt]=max(tree0[rt],max(tree0[lson],tree0[rson]));
tree0[rt]=max(tree0[rt],max(lmax0[rt],rmax0[rt]));
tree1[rt]=max(rmax1[lson]+lmax1[rson],max(tree1[lson],tree1[rson]));
tree1[rt]=max(tree1[rt],max(tree1[lson],tree1[rson]));
tree1[rt]=max(tree1[rt],max(lmax1[rt],rmax1[rt]));
}
void pushdown(int rt){
if(lazy[rt]){
swp(lson);
swp(rson);
lazy[lson]^=1;
lazy[rson]^=1;
lazy[rt]=0;
}
return;
}
void build(int rt,int l,int r){
lazy[rt]=0;
if(l==r){
scanf("%d",&a[l]);
if(a[l]==1){
tree0[rt]=0;tree1[rt]=1;
lmax0[rt]=0;rmax0[rt]=0;
lmax1[rt]=1;rmax1[rt]=1;
}
else{
tree0[rt]=1;tree1[rt]=0;
lmax0[rt]=1;rmax0[rt]=1;
lmax1[rt]=0;rmax1[rt]=0;
}
// cout<<l<<endl;
return;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(rt);
}
void change(int rt,int l,int r,int x,int y){
if(l>=x&&r<=y){
lazy[rt]^=1;
swp(rt);
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(x<=mid)change(lson,l,mid,x,y);
if(y>mid)change(rson,mid+1,r,x,y);
pushup(rt);
}
int query(int rt,int l,int r,int x,int y){
if(l>=x&&r<=y){
return tree1[rt];
}
int ans=0;
pushdown(rt);
int mid=(l+r)>>1;
if(x<=mid){ans=max(query(lson,l,mid,x,y),ans);}
if(y>mid){ans=max(query(rson,mid+1,r,x,y),ans);}
ans=max(ans,min(mid-x+1,rmax1[lson])+min(y-mid,lmax1[rson]));
return ans;
}
int main(){
while(~scanf("%d",&n)){
build(1,1,n);
scanf("%d",&m);
while(m--){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==0){
printf("%d\n",query(1,1,n,l,r));
}
else{
change(1,1,n,l,r);
}
// for(int i=1;i<=4*n;i++){
// printf("%d ",tree1[i]);
// }puts("");
}
}
}
#include <bits/stdc++.h>
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)
#define NS (100005)
using namespace std;
struct N {int l1, r1, m1, l0, r0, m0, tag;} e[NS << 2];
int n, m, arr[NS];
void Swp(int a)
{
swap(e[a].l1, e[a].l0);
swap(e[a].r1, e[a].r0);
swap(e[a].m1, e[a].m0);
}
void pup(int a)
{
int l = LS(a), r = RS(a);
if (!e[l].m0) e[a].l1 = e[l].l1 + e[r].l1;
else e[a].l1 = e[l].l1;
if (!e[r].m0) e[a].r1 = e[r].r1 + e[l].r1;
else e[a].r1 = e[r].r1;
if (!e[l].m1) e[a].l0 = e[l].l0 + e[r].l0;
else e[a].l0 = e[l].l0;
if (!e[r].m1) e[a].r0 = e[r].r0 + e[l].r0;
else e[a].r0 = e[r].r0;
e[a].m0 = max(e[l].r0 + e[r].l0, max(e[l].m0, e[r].m0));
e[a].m1 = max(e[l].r1 + e[r].l1, max(e[l].m1, e[r].m1));
}
void pdown(int a)
{
if (!e[a].tag) return;
Swp(LS(a)), Swp(RS(a));
e[LS(a)].tag ^= 1, e[RS(a)].tag ^=1, e[a].tag = 0;
}
void Build(int L = 1, int R = n, int a = 1)
{
memset(&e[a], 0, sizeof(N));
if (L == R)
{
if (arr[L]) e[a].l1 = e[a].r1 = e[a].m1 = 1;
else e[a].l0 = e[a].r0 = e[a].m0 = 1;
return;
}
int Mid = (L + R) >> 1;
Build(L, Mid, LS(a)), Build(Mid + 1, R, RS(a)), pup(a);
}
void Rev(int l, int r, int L = 1, int R = n, int a = 1)
{
if (l <= L && R <= r) {Swp(a), e[a].tag ^= 1; return;}
pdown(a); int Mid = (L + R) >> 1;
if (l <= Mid) Rev(l, r, L, Mid, LS(a));
if (r > Mid) Rev(l, r, Mid + 1, R, RS(a));
pup(a);
}
int Query(int l, int r, int L = 1, int R = n, int a = 1)
{
if (l <= L && R <= r) return e[a].m1;
pdown(a); int Mid = (L + R) >> 1, res = 0;
if (l <= Mid) res = max(res, Query(l, r, L, Mid, LS(a)));
if (r > Mid) res = max(res, Query(l, r, Mid + 1, R, RS(a)));
res = max(res, min(Mid - l + 1, e[LS(a)].r1) + min(r - Mid, e[RS(a)].l1));
return res;
}
int main(int argc, char const* argv[])
{
while (~scanf("%d", &n))
{
for (int i = 1; i <= n; i += 1) scanf("%d",&arr[i]);
Build();scanf("%d",&m);
for (int c = 1, o, l, r; c <= m; c += 1)
{
scanf("%d%d%d",&o,&l,&r);
if (o) Rev(l, r);
else printf("%d\n", Query(l, r));
}
}
return 0;
}
2019ICPC上海网络赛 - A. Lightning Routing I
网络赛的题，知识点略深可不看，下面有篇博客
https://blog.csdn.net/weixin_44059127/article/details/100941413
思路：动态维护直径+LCA
京公网安备 11010502036488号