#include<bits/stdc++.h> using namespace std; const int maxn = 0x3f3f3f3f; int mn[801000]; int cost[200100]; int dp[200100]; vector<int>v[200100]; void add_edge(int l,int r,int root){ if(l==r){ mn[root]=maxn;//叶子节点 return ; } int mid=(l+r)/2; add_edge(l,mid,root<<1);//递归构造左子树 add_edge(mid+1,r,(root<<1)+1);//递归构造右子树 mn[root]=min(mn[root<<1],mn[(root<<1)+1]);//根据左右子树根节点的值，更新当前根节点的值 } int query(int left,int right,int l,int r,int root){//区间查找，l和r表示当前区间端点，left和right表示查询区间端点 if(left<=l&&r<=right)//当前节点区间包含在查询区间内 return mn[root]; int mid=(l+r)/2; int res=maxn; if(left<=mid) res=min(res,query(left,right,l,mid,root<<1));//分别从左右子树查询，返回两者查询结果的较小值 if(right>mid) res=min(res,query(left,right,mid+1,r,(root<<1)+1)); return res; } void update(int pos/*待更新节点的标*/,int val/*更新的值*/,int l,int r,int root){//当前区间的端点 if(l==r){ mn[root]=min(mn[root],val);//找到了相应的节点，更新（这里更新的是叶子节点，会对父节点产生影响） return; } int mid=(l+r)/2; if(pos<=mid) update(pos,val,l,mid,root<<1);//在左子树中更新 else update(pos,val,mid+1,r,(root<<1)+1);//在右子树中更新 mn[root]=min(mn[root<<1],mn[(root<<1)+1]);//根据左右子树的值回溯更新当前节点的值 } int main(){ int n,q; int cnt=0; scanf("%d",&n); add_edge(1,n,1); for(int i=1,j;i<=n;i++){ scanf("%d",&j); cnt+=!j;//b中0的个数 cost[i]=j?1:-1;//当前bi为1即为1，bi为0即为-1，在加和前x位时即可得到bi为1的数量减去bi为零的数量 } scanf("%d",&q); for(int i=0,j,k;i<q;i++){ scanf("%d%d",&j,&k); v[j].push_back(k);//存下区间 } memset(dp,maxn,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++){ int ct = v[i].size();//左端点为i的区间的个数 for (int k = 0; k < ct;k++){ int j=v[i][k];//右端点 int tmp=dp[i-1]; tmp=min(tmp,query(max(i-1,1)/*i为1时仍为1，其他为i-1*/,j,1,n,1)); if(tmp<dp[j]){//存在更优解 dp[j]=tmp; update(j,tmp,1,n,1); } } dp[i]=min(dp[i],dp[i-1]+cost[i]);//cost[i]为1表示b[i]=1，cost[i]为-1表示b[i]=0，由于dp[i]表示a0b1-a0b0 } printf("%d\n",dp[n]+cnt);//cnt表示b0的数量 return 0; } /*题目要求求min{(a=0&&b=1)+(a=1&&b=0)}，即求min{(a=0&&b=1)+(b=0)-(a=0&&b=0)}， 即求b=0+min{(a=0&&b=1)-(a=0&&b=0)},dp[i]表示前i个数的min{(a=0&&b=1)-(a=0&&b=0)}*/ /*线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题 附上结构体区间更新的细节讲解http://www.cnblogs.com/TenosDoIt/p/3453089.html*/