今天成人礼。于是打算写点无营养鲜花。
口胡场都能被打自闭，真有你的。
一花 二乃 三玖 四叶 五月 六小.jpg
那你说的对。
猴戏世家
P4737。
场上脑抽，想到了后一半，没想到前一半。死于一直想从下到上扫描线无果，然后开始想怎么在线做。
从上到下扫描线，然后开个 set 维护栅栏。扫到一个点：
- 猴：找到右边第一个栅栏，就是它的。
- 栅栏：插入 set。
这样我们找到了每个栅栏包含哪些点。然后对于一个栅栏，它完全包含的在它后边加入的栅栏也是算作它的答案里的。这玩意显然成一个树形结构。于是并查集倒着扫一遍询问就行了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
set<pair<int,int> >s;
int n,m,ans[300010],fa[300010],size[300010],f[300010];
struct node{
int x,y,od;
bool operator<(const node&s)const{
return y==s.y?od>s.od:y>s.y;
}
}p[600010];
int find(int x){
return f[x]==x?f[x]:f[x]=find(f[x]);
}
void merge(int x,int y){
x=find(x);y=find(y);
if(x==y)return;
f[y]=x;size[x]+=size[y];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d%d",&p[n+i].x,&p[n+i].y),p[n+i].od=i,f[i]=i;
sort(p+1,p+n+m+1);
for(int i=1;i<=n+m;i++){
if(p[i].od){
s.insert(make_pair(p[i].x,p[i].od));
set<pair<int,int> >::iterator it=s.find(make_pair(p[i].x,p[i].od));
if(++it!=s.end())fa[p[i].od]=it->second;
while(1){
it=s.find(make_pair(p[i].x,p[i].od));
if(it==s.begin())break;
--it;
if(it->second>p[i].od)s.erase(it);
else break;
}
}
else{
set<pair<int,int> >::iterator it=s.lower_bound(make_pair(p[i].x,0));
if(it!=s.end())size[it->second]++;
}
}
for(int i=m;i>=1;i--){
ans[i]=size[find(i)];
if(fa[i])merge(fa[i],i);
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
零糖麦片
CF468E。
啊这。
首先这玩意叫积和式不叫集合式。然后算这玩意没多项式复杂度解法。
然后好深奥，等我写完再说。
文体双花
线段树扫描线 + 单调栈。签到题，具体参考 pudding monsters。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <queue>
#define int long long
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int mod=1000000007;
int n,p[100010],dp[100010];
struct node{
int min,cnt;
node operator+(const int &s)const{
return{min+s,cnt};
}
node friend operator+(node s,node t){
node ret={};
ret.min=std::min(s.min,t.min);
if(ret.min==s.min)ret.cnt+=s.cnt;
if(ret.min==t.min)ret.cnt+=t.cnt;
ret.cnt%=mod;
return ret;
}
};
struct Seg{
int lz;
node val;
}tree[400010];
void pushup(int rt){
tree[rt].val=tree[lson].val+tree[rson].val;
}
void pushtag(int rt,int val){
tree[rt].val=tree[rt].val+val;tree[rt].lz+=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);
pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
pushup(rt);
}
void updatecnt(int rt,int L,int R,int pos,int val){
if(L==R){
tree[rt].val.cnt=val;return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(pos<=mid)updatecnt(lson,L,mid,pos,val);
else updatecnt(rson,mid+1,R,pos,val);
pushup(rt);
}
node query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[rt].val;
int mid=(L+R)>>1;
node val={0x3f3f3f3f,0};
if(l<=mid)val=val+query(lson,L,mid,l,r);
if(mid<r)val=val+query(rson,mid+1,R,l,r);
return val;
}
int stk1[100010],stk2[100010],top1,top2;
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
dp[0]=1;
for(int i=1;i<=n;i++){
updatecnt(1,1,n,i,dp[i-1]);
while(top1&&p[i]<=p[stk1[top1]]){
update(1,1,n,stk1[top1-1]+1,stk1[top1],p[stk1[top1]]);
top1--;
}
while(top2&&p[i]>=p[stk2[top2]]){
update(1,1,n,stk2[top2-1]+1,stk2[top2],-p[stk2[top2]]);
top2--;
}
update(1,1,n,stk1[top1]+1,i,-p[i]);
update(1,1,n,stk2[top2]+1,i,p[i]);
stk1[++top1]=stk2[++top2]=i;
update(1,1,n,i,i,i);
dp[i]=query(1,1,n,1,i).cnt;
}
printf("%lld\n",dp[n]);
return 0;
}