小红的01子序列构造（hard）

package com.haust.hj;

import java.util.*;
/**

核心关系式:
若两个相邻区间:[a,b](有xa个0,ya个1,ka个01子序列), [b+1,c](有xb个0,yb个1,kb个01子序列)
则合成的新区间:[a,c]有ka+kb+xa*yb个01子序列.
若已知一个区间的0个数和1个数, 则当它左侧全为0, 右侧全为1时, 有最大的01子序列个数, 最大值为0、1个数的乘积,反之为0.

证明：
 区间[a,b]中的排序分别为[o1 l1 o2 l2 ...... on ln]，其中oi为第i次出现字符连续为0的串,li是为1
 o = o1 + o2 + ... +on
 l = l1 + l2 + ... +ln
 则有通式: ka = (o1+o2+......+on)*ln + (o1+o2+......+on-1)*ln-1 + ...... + o1*l1
 即 1的长度在0-ln的可能 加上 1的长度在ln-(ln+ln-1)的可能 加上 ...... 加上 1的长度在(l-l1)-l的可能
 显然有 ka<=o*l
 (o1+o2+......+on)*ln + (o1+o2+......+on-1)*ln-1 + ...... + o1*l1<= (o1 + o2 + ... +on)*(l1 + l2 + ... +ln)
 =(o1 + o2 + ... +on)*ln + (o1 + o2 + ... +on)*(ln-1) + ......+ (o1 + o2 + ... +on)*l1
 当且仅当 它左侧全为0, 右侧全为1时, 有最大的01子序列个数, 最大值为0、1个数的乘积,即ka=o*l.
 在根据通式: ka = (o1+o2+......+on)*ln + (o1+o2+......+on-1)*ln-1 + ...... + o1*l1
 易知区间:[a,c]的 k=ka+kb+xa*yb；



 解题:
 对于两个大小区间, D1:[li,ri],D2:[lj,rj], 小区间D1包含于大区间D2, 即lj<=li<=ri<=rj.
 把大区间分成三份:
 [lj,li):长度为n=li-lj, 有xa个0、ya个1、ka个01子序列,
 [li,ri]:长度为l=ri-li+1, 有xi个0、yi个1、ki个01子序列,
 (ri,rj]:长度为m=rj-ri, 有xb个0、yb个1、kb个01子序列,
 则有等式: k = xa*yi + xi*yb + xa*yb + ka + kb + ki
 其中,已知: ki, k, xi, yi, 和区间的 li, ri, lj, rj
 和等式 xi+xa+xb, lr-li+1 = xa+ya, li-rj+1 =xb+yb
 我们只需要枚举xa的个数，就能计算出清楚xb,ya,yb.
 k = xa*yi + xi*yb + xa*yb + ka + kb + ki
 而 0 <= ka + kb <= xa*ya + xb*yb
 所以当大区间的k确定时,我们只需要枚举到一个合适的xa,并尽量的把 ka最大,就能算出其中的一个结果。


*/

class Par{
    int l;
    int r;
    int index;

    public Par (int a , int b, int c){
        l = a;
        r = b;
        index = c;
    }

    @Override
    public String toString() {
        return "l:"+l+",r:"+r+",index:"+index;
    }
}
public class HJ119 {

    //给出区间[l , r],零的个数为cnt0,一的个数为r-l+1-cnt0,字串为k的字符串
    static void fill(int l, int r, int cnt0, int k, int[] ans) {
        int cnt1 = r - l + 1 - cnt0;
        for (int i = l; i <= r; i++) {
            if (k >= cnt1) k -= cnt1;
            else {
                ans[i] = 1;
                cnt1--;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] ans = new int[n+1];
        int[] l = new int[m+1];
        int[] r = new int[m+1];
        int[] a = new int[m+1];
        int[] b = new int[m+1];
        int[] c = new int[m+1];

        ArrayList<Par> list = new ArrayList<>();

        for (int i = 1; i <= m; i++) {
            l[i] = in.nextInt();
            r[i] = in.nextInt();
            a[i] = in.nextInt();
            b[i] = in.nextInt();
            c[i] = in.nextInt();
            list.add(new Par(l[i],r[i],i));
        }

        Collections.sort(list, new Comparator<Par>() {
            @Override
            public int compare(Par o1, Par o2) {
                if (o1.l > o2.l)
                    return -1;
                if(o1.l==o2.l)
                    return o1.r - o2.r;
                return 1;
            }
        });

        for (int i = 1; i < l.length; i++) {
            System.out.println();
            System.out.println(l[i] + "," + r[i] + "," + a[i] + "," + b[i] + "," + c[i]);
            System.out.println(list.get(i-1).toString());
        }

        for (int i = 1; i <= m; i++) {

            int p = list.get(i-1).index;
            int pre;
            if(i==1) pre = 0;
            else pre = list.get(i-2).index;
            int prel = l[pre];
            int prer=r[pre];
            int lenl = l[pre]-l[p];
            int lenr = r[p]-r[pre];
            int basea=a[pre],baseb=b[pre],basec=c[pre];
            if(i==1) {
                lenl = 0;
                lenr = r[p] - l[p] + 1;
                basea = baseb = basec = 0;
            }
            int cnt0 = a[p] - basea;
            Boolean flag = false;
            for (int x = 0; x <= Math.min(cnt0, lenl); x++) {
                int cnt0l = x, cnt0r = cnt0 - x;
                int cnt1l = lenl - cnt0l;
                int cnt1r = lenr - cnt0r;
                // k - ka -kb
                int basek = basec + cnt0l * baseb + cnt1r * basea + cnt0l * cnt1r;
                // ka,ba取最大的值,即xa*ya + xb*yb
                int addonk = cnt0l * cnt1l + cnt0r * cnt1r;
                if (cnt1l < 0 || cnt1r < 0) continue;
                // k = xa*yi + xi*yb + xa*yb + ka + ba + ki 而 0 <= ka+kb <= xa*ya + xb*yb
                if (c[p] > basek + addonk || c[p] < basek) continue;
                flag = true;
                int addon = c[p] - basek;
                // 尽量的把 ka最大
                if (addon <= cnt0l * cnt1l) {
                    fill(l[p], l[p] + lenl - 1, cnt0l, addon, ans);
                    fill(r[p] - lenr + 1, r[p], cnt0r, 0, ans);
                } else {
                    fill(l[p], l[p] + lenl - 1, cnt0l, cnt0l * cnt1l, ans);
                    fill(r[p] - lenr + 1, r[p], cnt0r, addon - cnt0l * cnt1l, ans);
                }
                break;
            }
            if(!flag){
                System.out.println(-1);
                return;
            }
        }

        for(int i=1;i<=n;i++) System.out.print(ans[i]);

    }

}