P1527 [national training team] matrix multiplication (overall dichotomy)

Classic example of overall dichotomy.

For the overall dichotomy, my personal understanding is dichotomy answer set dichotomy.

Specifically, the answer is divided into two parts, and then the query is divided into two parts, which is similar to the division and treatment method of finding the largest interval \ (k \) in the weight line segment tree.

First of all, our violent approach is to run aside and give two answers to each question. The complexity is O(\(nm log n \))

This is obviously unacceptable to us.

We found that when we deal with each query, we will repeatedly calculate the weighting operation many times.

Let's consider processing the queries together, and each weighting operation is only repeated once.

This will save a lot of time. How to achieve it?

Suppose that the answer we dichotomize is \ (mid \), then the answer we ask is divided into two cases

One is that if the answer is less than \ (mid \), we can continue recursion,

Like this:

The answer to this question is purple.

The other is the query greater than \ (mid \), so we need to subtract the contribution on the left and recurse in the range of \ (mid - R \) (refer to the method of solving the largest interval \ (k \) in the weight line segment tree).

Like this

We put the question with the answer on the left of \ (mid \) in the front and the question with the answer on the right of \ (mid \) in the back.

In this way, we can recurse the interval of \ (L-mid \) in the former part and the interval of \ (mid - R \) in the latter part. (that is, divide and conquer inquiries)

For this question, how can we judge whether the answer to this question is greater than or less than \ (mid \)?

We can use the two-dimensional tree array to add the weighting operation of this part of \ (L-mid \), and then each query is equivalent to two-dimensional points.

If the number of points in this interval is greater than \ (q[i].c \), we mean that the answer is less than \ (mid \), otherwise it is greater than \ (mid \)

One thing to note is that when dividing the query into two parts, you must first subtract the contribution of \ (L-mid \) and assign it to the transition array in the middle (I stuck here for nearly an hour)

In addition, the variables that record the number of queries in the front and back parts, such as \ (cntl\), \(cntr \) should be set as local variables, otherwise they will be added all the time, causing you to make mistakes in your answer

The specific code is as long as this (code with comments)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 300000;
int n,m,tot;
int a[510][510],tr[510][510],ans[N],b[N];
struct node{ int x,y;};
struct kkk
{
	int x1,x2,id;
	int y1,y2,c;
}q[N],tong[N],stal[N],star[N];
vector< node > sta[N];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
int lowbit(int x){return x & -x;}
void chenge(int x,int y,int val)//Two dimensional tree array
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        for(int j = y; j <= n; j += lowbit(j))
        {
            tr[i][j] += val;
        }
    }
}
int ask(int x,int y)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
    {
        for(int j = y; j; j -= lowbit(j))
        {
            res += tr[i][j];
        }
    }
    return res;
}
int get_ans(int x1,int y1,int x2,int y2)//Two dimensional point counting
{
    return (ask(x2,y2) + ask(x1-1,y1-1) - ask(x1-1,y2) - ask(x2,y1-1));
}
void work(int l,int r,int L,int R)//L-R is the interval of our answers, and L-R is our query interval
{
    int cntl = 0, cntr = 0;//These two variables must be set as local variables
    if(l == r)//l==r means that the answer to our L-R part is l
    {
        for(int i = L; i <= R; i++)
        {
            ans[q[i].id] = l;
        }
        return;
    }
    int mid = (l+r)>>1;//Dichotomous answer
    for(int i = l; i <= mid; i++)
    {
        for(int j = 0; j < (int)sta[i].size(); j++)
        {
            int x = sta[i][j].x;
            int y = sta[i][j].y;
            chenge(x,y,1);//Weighting operation
        }
    }
    for(int i = L; i <= R; i++)
    {
        int tmp = get_ans(q[i].x1,q[i].y1,q[i].x2,q[i].y2);//Two dimensional point counting
        if(tmp >= q[i].c)//If the number of points in this area is greater than Q [i] C shows that the answer to our question is less than mid, so we should put him in the first part
        {
            stal[++cntl] = q[i];
        }
        else 
		{
        	q[i].c -= tmp;//The latter part first subtracts the contribution of the answer of l-mid and divides the answer in the interval of de mid - r
        	star[++cntr] = q[i];//Divide him into the back part
        }
    }
    for(int i = l; i <= mid; i++)//Restore weighting operation
    {
        for(int j = 0; j < sta[i].size(); j++)
        {
            int x = sta[i][j].x;
            int y = sta[i][j].y;
            chenge(x,y,-1);
        }
    }
    for(int i = L; i <= L + cntl - 1 ; i++) q[i] = stal[i - L + 1];//Re order the questions and put the answers that are less than mid in the front and vice versa
    for(int i = L + cntl; i <= R; i++) q[i] = star[i - L - cntl + 1];
    work(l,mid,L,L + cntl - 1); work(mid + 1,r,L + cntl,R);//Continue recursion
}
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            a[i][j] = read();
            b[++tot] = a[i][j];
        }
    }
    sort(b + 1,b + tot + 1);//Discretization
    int t = unique(b + 1,b + tot + 1) - b - 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            a[i][j] = lower_bound(b+1,b+t+1,a[i][j]) - b;
            sta[a[i][j]].push_back((node){i,j});//Record the position where each weight appears
        }
    }
    for(int i = 1; i <= m; i++)
    {
        q[i].x1 = read(); q[i].y1 = read();
        q[i].x2 = read(); q[i].y2 = read();
        q[i].c = read();  q[i].id = i;
    }
    work(1,t,1,m);//Overall dichotomy
    for(int i = 1; i <= m; i++)
    {
        printf("%d\n",b[ans[i]]);
    }
    return 0;
}

Tags: Binary Indexed Tree partitioning

Posted by knetcozd on Thu, 19 May 2022 20:11:52 +0300