hdu 1698 Just a Hook (³É¶Î¸üÐÂ+×ÜÇø¼äÇóºÍ)

Just a Hook

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18411 Accepted Submission(s): 9231


Problem Description In the game of DotA, Pudge¡¯s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.



Now Pudge wants to do some Z†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcGVyYXRpb25zIG9uIHRoZSBob29rLjxicj4KPGJyPgpMZXQgdXMgbnVtYmVyIHRoZSBjb25zZWN1dGl2ZSBtZXRhbGxpYyBzdGlja3Mgb2YgdGhlIGhvb2sgZnJvbSAxIHRvIE4uIEZvciBlYWNoIG9wZXJhdGlvbiwgUHVkZ2UgY2FuIGNoYW5nZSB0aGUgY29uc2VjdXRpdmUgbWV0YWxsaWMgc3RpY2tzLCBudW1iZXJlZCBmcm9tIFggdG8gWSwgaW50byBjdXByZW91cyBzdGlja3MsIHNpbHZlciBzdGlja3Mgb3IgZ29sZGVuIHN0aWNrcy48YnI+ClRoZSB0b3RhbCB2YWx1ZSBvZiB0aGUgaG9vayBpcyBjYWxjdWxhdGVkIGFzIHRoZSBzdW0gb2YgdmFsdWVzIG9mIE4gbWV0YWxsaWMgc3RpY2tzLiBNb3JlIHByZWNpc2VseSwgdGhlIHZhbHVlIGZvciBlYWNoIGtpbmQgb2Ygc3RpY2sgaXMgY2FsY3VsYXRlZCBhcyBmb2xsb3dzOjxicj4KPGJyPgpGb3IgZWFjaCBjdXByZW91cyBzdGljaywgdGhlIHZhbHVlIGlzIDEuPGJyPgpGb3IgZWFjaCBzaWx2ZXIgc3RpY2ssIHRoZSB2YWx1ZSBpcyAyLjxicj4KRm9yIGVhY2ggZ29sZGVuIHN0aWNrLCB0aGUgdmFsdWUgaXMgMy48YnI+Cjxicj4KUHVkZ2Ugd2FudHMgdG8ga25vdyB0aGUgdG90YWwgdmFsdWUgb2YgdGhlIGhvb2sgYWZ0ZXIgcGVyZm9ybWluZyB0aGUgb3BlcmF0aW9ucy48YnI+CllvdSBtYXkgY29uc2lkZXIgdGhlIG9yaWdpbmFsIGhvb2sgaXMgbWFkZSB1cCBvZiBjdXByZW91cyBzdGlja3MuPGJyPgoKCiAKPGJyPgoKSW5wdXQKClRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyB0aGUgbnVtYmVyIG9mIHRoZSBjYXNlcy4gVGhlcmUgYXJlIG5vIG1vcmUgdGhhbiAxMCBjYXNlcy48YnI+CkZvciBlYWNoIGNhc2UsIHRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMTw9Tjw9MTAwLDAwMCwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiB0aGUgc3RpY2tzIG9mIFB1ZGdloa9zIG1lYXQgaG9vayBhbmQgdGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgUSwgMDw9UTw9MTAwLDAwMCwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiB0aGUgb3BlcmF0aW9ucy48YnI+Ck5leHQgUSBsaW5lcywgZWFjaCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIFgsIFksIDE8PVg8PVk8PU4sIFosIDE8PVo8PTMsIHdoaWNoIGRlZmluZXMgYW4gb3BlcmF0aW9uOiBjaGFuZ2UgdGhlIHN0aWNrcyBudW1iZXJlZCBmcm9tIFggdG8gWSBpbnRvIHRoZSBtZXRhbCBraW5kIFosIHdoZXJlIFo9MSByZXByZXNlbnRzIHRoZSBjdXByZW91cyBraW5kLCBaPTIgcmVwcmVzZW50cyB0aGUgc2lsdmVyIGtpbmQgYW5kIFo9MyByZXByZXNlbnRzCiB0aGUgZ29sZGVuIGtpbmQuPGJyPgoKCiAKPGJyPgoKT3V0cHV0CgpGb3IgZWFjaCBjYXNlLCBwcmludCBhIG51bWJlciBpbiBhIGxpbmUgcmVwcmVzZW50aW5nIHRoZSB0b3RhbCB2YWx1ZSBvZiB0aGUgaG9vayBhZnRlciB0aGUgb3BlcmF0aW9ucy4gVXNlIHRoZSBmb3JtYXQgaW4gdGhlIGV4YW1wbGUuPGJyPgoKCiAKPGJyPgoKU2FtcGxlIElucHV0Cgo8cHJlIGNsYXNzPQ=="brush:java;">1 10 2 1 5 2 5 9 3
Sample Output

Case 1: The total value of the hook is 24.

ÌâÒâºÜ¼òµ¥£¬Çó×ÜÇø¼äµÄºÍ¡£Ã¿´Î¸üÐÂʱ²»Òª¸üе½µ×²ã¾ÍÐУ¬¸üÐÂÍê³Éʱ˳±ãÇóºÍ¾ÍÐС£×îºóf[1].s¼´ÊÇans.

#include
#include
#include
#include
#include
using namespace std;
#define ll __int64
#define N 200005
struct node
{
    int l,r;
    int s,v,f;  //Çø¼äºÍ¡¢¸ÃÇø¼äµÄµ¥¸öµãµÄÖµ¡¢fΪ²»ÁãÔò¸ÃÇø¼äÓдý¸üÐÂÖµ
}f[N*3];
void creat(int t,int l,int r)
{
    f[t].l=l;
    f[t].r=r;
    f[t].v=1;
    f[t].f=0;
    if(l==r)
    {
        f[t].s=1;
        return ;
    }
    int tmp=t<<1,mid=(l+r)>>1;
    creat(tmp,l,mid);
    creat(tmp|1,mid+1,r);
    f[t].s=f[tmp].s+f[tmp|1].s;
}
void update(int t,int l,int r,int v)
{
    int tmp=t<<1,mid=(f[t].l+f[t].r)>>1;
    if(f[t].l==l&&f[t].r==r)
    {
        f[t].v=f[t].f=v;      
        f[t].s=(r-l+1)*v;
        return ;
    }
    if(f[t].f)      //ÏòϸüÐÂ
    {
        f[tmp].f=f[tmp|1].f=f[t].f;
        f[tmp].v=f[tmp|1].v=f[t].f;
        f[tmp].s=(f[tmp].r-f[tmp].l+1)*f[t].f;
        f[tmp|1].s=(f[tmp|1].r-f[tmp|1].l+1)*f[t].f;
        f[t].f=0;
    }
    if(r<=mid)
        update(tmp,l,r,v);
    else if(l>mid)
        update(tmp|1,l,r,v);
    else
    {
        update(tmp,l,mid,v);
        update(tmp|1,mid+1,r,v);
    }
    f[t].s=f[tmp].s+f[tmp|1].s;      //ÏòÉÏÇóºÍ
    f[t].f=0;
}
int main()
{
    int T,i,n,q,cnt=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&q);
        creat(1,1,n);
        while(q--)
        {
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);
            update(1,l,r,v);
        }
        printf("Case %d: The total value of the hook is %d.\n",cnt++,f[1].s);
    }
    return 0;
}