题面描述：尽可能多的放置符合要求的炸弹。
分析：
在i,j处放置炸弹，则在第i行，上一个硬石头之后，下一个硬石头之前，第j列，上一个硬石头之后，下一个硬石头之前，不能再次放置炸弹。
首先，这个题，一看很显然就是一道网络流的题面。
那么，我们可以这样想，硬石头与硬石头之间建立二分图，而如何建立呢？
假设在i,j处放炸弹，那么，一定是在第i行上一个硬石头之后，那么我们可以建一条边，从源点连向第i行上一个硬石头，流量为1。
那么为了保证j列同样满足性质，则可以建立一个边，从第j列上一个硬石头连向汇点，流量同样为1。
同时，为了保证i,j同时被选择，则可以将第i行的上一个硬石头连向第j列的上一个硬石头，流量为1。
那么这样可以保证题面要求的性质么？答案是肯定的。因为如果i,j的上一个硬石头间存在一个可以放置的点，那么就一定被选择，而如果存在多个，则只能选择一个，根据贪心，之后反悔的原则，可以将答案求出。
之后跑一遍dinic就可以了
代码附上：
#include#include #include #include #include #include #include using namespace std;#define N 10005#define maxn 1000000000#define lson l,m,tr[rt].ls#define rson m+1,r,tr[rt].rsstruct node{ int ls,rs,siz;}tr[N*400];int rot[N*400],n,Q,nx,ny,rx[N],ry[N],cnt,v[N];char s[N];void insert(int x,int l,int r,int &rt,int v,int c){ if(!rt)rt=++cnt; if(l==r) { tr[rt].siz=tr[x].siz+c; return ; } int m=(l+r)>>1; if(v<=m)tr[rt].rs=tr[x].rs,insert(tr[x].ls,lson,v,c); else tr[rt].ls=tr[x].ls,insert(tr[x].rs,rson,v,c); tr[rt].siz=tr[tr[rt].ls].siz+tr[tr[rt].rs].siz;}int query(int l,int r,int k){ if(l==r)return l; int m=(l+r)>>1,sizls=0; for(int i=1;i<=nx;i++)sizls-=tr[tr[rx[i]].ls].siz; for(int i=1;i<=ny;i++)sizls+=tr[tr[ry[i]].ls].siz; if(k<=sizls) { for(int i=1;i<=nx;i++)rx[i]=tr[rx[i]].ls; for(int i=1;i<=ny;i++)ry[i]=tr[ry[i]].ls; return query(l,m,k); }else { for(int i=1;i<=nx;i++)rx[i]=tr[rx[i]].rs; for(int i=1;i<=ny;i++)ry[i]=tr[ry[i]].rs; return query(m+1,r,k-sizls); }}int main(){ scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); for(int j=i;j<=n;j+=(j&(-j)))insert(rot[j],0,maxn,rot[j],v[i],1); } while(Q--) { int x,y,z; scanf("%s%d%d",s,&x,&y); if(s[0]=='C') { for(int i=x;i<=n;i+=(i&(-i)))insert(rot[i],0,maxn,rot[i],v[x],-1); v[x]=y; for(int j=x;j<=n;j+=(j&(-j)))insert(rot[j],0,maxn,rot[j],v[x],1); }else { scanf("%d",&z); nx=ny=0; for(int j=x-1;j;j-=(j&(-j))) { rx[++nx]=rot[j]; } for(int j=y;j;j-=(j&(-j))) { ry[++ny]=rot[j]; } printf("%d\n",query(0,maxn,z)); } } return 0;}