|
1.关押罪犯
思路：将每个罪犯分成两个点，一个是他本身，另一个是表示不与他一个监狱的点，从高到低排序每对罪犯的怨气值，每次先查询两个罪犯是否在一个牢房，若在直接输出，反之将两个人相互与对方表示不再一个牢房的点连边
2.hotel
思路：建立线段树，每个节点保存本段最长，靠左最长，靠右最长，每次修改时记录懒标记区间修改，然后用儿子节点的值更新父亲节点；查询时先选择左儿子，再选择区间跨越左右两个节点，最后选择右儿子
3.picture
思路：扫描线，因为每次修改都会导致边长的变化，所以答案要加上边长变化的值，扫描线横着扫一次，竖着扫一次后相加得出答案
void build(int id,int l,int r){
tr[id].l=l;
tr[id].r=r;
tr[id].ans=tr[id].cs=0;
if(l+1==r) return ;//扫描线的线段树存放的是线段，所以长度不能相等
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid,r);
}
void insert(int id,int x,int y,int w){
int l=tr[id].l,r=tr[id].r;
if(l>=x&&r<=y){
tr[id].cs+=w;
if(tr[id].cs) tr[id].ans=r-l;//只有线段没有被覆盖才会用儿子节点更新
else tr[id].ans=(l==r?0:tr[id<<1].ans+tr[id<<1|1].ans);
return ;
}
int mid=(l+r)>>1;
if(x<tr[id<<1].r) insert(id<<1,x,y,w);
if(y>tr[id<<1|1].l) insert(id<<1|1,x,y,w);
tr[id].ans=(tr[id].cs?tr[id].ans:tr[id<<1].ans+tr[id<<1|1].ans);
}
4.作诗
思路：分块，并且记录以i结尾的块数字出现次数的前缀和，并且统计l~r块中答案，每次询问时候答案初始为ans[id[l]+1][id[r]-1]，在答案的基础上枚举不成整块的数的出现次数修改答案
struct fk{
int sum[350][100010],n,id[100100],l[350],r[350],len,w[1000010],ans[350][350],cnt[100010];
void init(){
for(int i=1;i<=n;i++){
id[i]=(i-1)/len+1;
}
for(int i=1;i<=n/len;i++){
l[i]=r[i-1]+1;
r[i]=i*len;
}
if(n%len){
l[n/len+1]=r[n/len]+1;
r[n/len+1]=n;
}
for(int i=1;i<=n;i++){//记录前缀和
if(id[i]!=id[i-1]){
for(int j=1;j<=n;j++){
sum[id[i]][j]=sum[id[i]-1][j];
}
}
sum[id[i]][w[i]]++;
}
for(int i=1;i<=ceil((double)n/len);i++){//统计答案，每次答案都从ans[i][j-1]上更新
for(int j=i;j<=ceil((double)n/len);j++){
ans[i][j]=ans[i][j-1];
for(int k=l[j];k<=r[j];k++){
int p=w[k];
cnt[p]++;
int gs=sum[j-1][p]-sum[i-1][p];
if((gs+cnt[p])%2==0&&(gs+cnt[p])) ans[i][j]++;//成偶数++；
else if((gs+cnt[p])>1) ans[i][j]--;//反之从以前加的上减去
}
for(int k=l[j];k<=r[j];k++){
int p=w[k];
cnt[p]--;
}
}
}
}
int query(int le,int ri){
int num=0;
if(id[le]==id[ri]){
for(int i=le;i<=ri;i++){
int p=w[i];
cnt[p]++;
if(cnt[p]%2==0) num++;
else if(cnt[p]>1&&cnt[p]%2==1) num--;
}
for(int i=le;i<=ri;i++) cnt[w[i]]--;
return num;
}
num=ans[id[le]+1][id[ri]-1];
//cout<<"*"<<num<<endl;
for(int i=le;i<=r[id[le]];i++){
int p=w[i];
cnt[p]++;
int gs=sum[id[ri]-1][p]-sum[id[le]][p];
if((gs+cnt[p])%2==0) num++;
else if((gs+cnt[p])>1) num--;
}
for(int i=l[id[ri]];i<=ri;i++){
int p=w[i];
cnt[p]++;
int gs=sum[id[ri]-1][p]-sum[id[le]][p];
if((gs+cnt[p])%2==0) num++;
else if((gs+cnt[p])>1) num--;
}
for(int i=le;i<=r[id[le]];i++) cnt[w[i]]--;
for(int i=l[id[ri]];i<=ri;i++) cnt[w[i]]--;
return num;
}
};
5.race
思路：先用点分治找到所有权值和等于k的链的左右端点，然后再在树上跑lca查询到两个节点的距离更新答案
void get_ans(int x){/点分治
d[x]=0;
id[x]=x;
cnt=0;
num[++cnt]=x;
for(int i=0;i<tu[x].size();i++){
int p=tu[x][i].p;
int w=tu[x][i].w;
if(vis[p]) continue;
get_d(p,x,w,p);
}
sort(num+1,num+cnt+1,cmp);
int l=1,r=cnt;
while(l<r){
if(d[num[l]]+d[num[r]]>w){
r--;
continue;
}
if(d[num[l]]+d[num[r]]<w){
l++;
continue;
}
if(id[num[l]]==id[num[r]]){
l++;
continue;
}
if(!mp[num[l]][num[r]]){//满足相等且不在一个子树的节点
mp[num[l]][num[r]]=true;
ans_cnt++;
ans[ans_cnt].from=num[l];
ans[ans_cnt].to=num[r];//记录下节点所在链的左右端点
l++;
}else{
l++;
}
}
}
6.营业额统计
用treap维护数据并且查询每个数的前驱和后继，要求绝对值最小，就取最后一个比他大的和第一个比他小的分别与其做差更新答案
struct treap{
int rnd[50010],sz[50001],w[50001],gs[50010],l[50001],r[50001],size,root,ans;
void pushup(int x){
sz[x]=sz[l[x]]+sz[r[x]]+gs[x];
}
void lr(int &k){
int t=r[k];
r[k]=l[t];
l[t]=k;
sz[t]=sz[k];
pushup(k);
k=t;
}
void rr(int &k){
int t=l[k];
l[k]=r[t];
r[t]=k;
sz[t]=sz[k];
pushup(k);
k=t;
}
void insert(int &k,int x){
if(!k){
size++;
k=size;
w[k]=x;
sz[k]=1;
rnd[k]=rand();
gs[k]=1;
return ;
}
sz[k]++;
if(w[k]==x){
gs[k]++;
}else{
if(x>w[k]){
insert(r[k],x);
if(rnd[k]<rnd[r[k]]) lr(k);
}else{
insert(l[k],x);
if(rnd[k]<rnd[l[k]]) rr(k);
}
}
}
void get_pre(int k,int x){//treap查前驱
if(!k) return ;
if(w[k]==x){
ans=k;
return ;
}
if(w[k]<x){
ans=k;//比他小就更新答案
get_pre(r[k],x);
}else{
get_pre(l[k],x);
}
}
void get_sub(int k,int x){//treap查后继
if(!k) return ;
if(w[k]==x){
ans=k;
return ;
}
if(w[k]>x){
ans=k;
get_sub(l[k],x);
}else{
get_sub(r[k],x);
}
}
};
?7.mokia
思路：cdq分治，将查询区间转换为二维前缀和（a[l1][r1]~a[l2][r2]=sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][l2-1])，然后用cdq分治（时间，x，y）三维偏序解决
void cdq(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
for(int i=l;i<=mid;i++) p1[i]=p[i];
for(int i=mid+1;i<=r;i++) p2[i]=p[i];
sort(p1+l,p1+mid+1,cmp);
sort(p2+mid+1,p2+r+1,cmp);
int x=l;
for(int i=mid+1;i<=r;i++){
if(p2[i].op==1) continue;
while(p1[x].x<=p2[i].x&&x<=mid){
if(p1[x].op==2){
x++;
continue;
}
ty.insert(p1[x].y,p1[x].w);
x++;
}
ans[p2[i].id]=ans[p2[i].id]+p2[i].w*ty.query(p2[i].y);
}
for(int i=l;i<x;i++){
if(p1[i].op==1){
ty.erase(p1[i].y,p1[i].w);
}
}
}
?
|